#!/usr/bin/python

from math import atan2, sqrt, floor, ceil, pi, hypot, degrees
pi2 = 2*pi

def isect(x1,y1, x2,y2, x3,y3, x4,y4):

    den = (y4-y3)*(x2-x1) - (x4-x3)*(y2-y1)
    t1n = (x4-x3)*(y1-y3) - (y4-y3)*(x1-x3)
    t2n = (x2-x1)*(y1-y3) - (y2-y1)*(x1-x3)

    if den != 0: # LINES NOT PARALLEL
        t1 = t1n / den
        t2 = t2n / den
        return  0<=t1<=1 and 0<=t2<=1 # INTERSECTIONS WITHIN SEGMENTS
    else:  # LINES PARALLEL
        if (t1n==0.0 and t2n==0): # LINES COINCIDENT

            if x1 == x2:    # VERTICAL LINES
                sep = max(y1,y2)<min(y3,y4) or min(y1,y2)>max(y3,y4)
            else:
                sep = max(x1,x2)<min(x3,x4) or min(x1,x2)>max(x3,x4)

            return not sep
        
        else: # LINES NOT COINCIDENT
            return False

def isects(x1,y1,x2,y2, lines):
    for line in lines:
        if isect(x1,y1,x2,y2,*line):
            # print x1,y1,x2,y2,line
            return True
    return False


def linelength(x1,y1, x2,y2):
    return hypot(x2-x1,y2-y1)

def line2angle(x1,y1, x2,y2):
    dx = x2-x1
    dy = y2-y1
    angle = atan2(dy,dx) # between -PI and PI
    if angle < 0:
        angle += pi2
    return degrees(angle)

def angle2speed(a, speeds):
    a0 = int(floor(a))
    a1 = int(ceil(a))
    f = a-a0
    return f*speeds[a1] + (1-f)*speeds[a0]

def line2time(x1,y1, x2,y2, speeds):
    angle = line2angle(x1,y1, x2,y2)
    speed = angle2speed(angle, speeds)
    length = linelength(x1,y1, x2,y2)

    if speed == 0:
        raise "Cannot sail into direction %f!" % angle
    
    return length / speed

def route_time(route_l, speeds):
    try:
        ts = int(sum([line2time(x1,y1, x2,y2, speeds)
                      for (x1, y1, x2, y2) in route_l])*3600)
        ts += (len(route_l) - 1) * 60

        h, m = divmod(ts, 3600)
        m, s = divmod(m, 60)

        return "%dh %dm %ds" % (h,m,s)
    except Exception, e:
        print e
        return "DNF" # Did not finish
        
# Check if route is OK

def route_travels_task_points(task_p, route_p): 
    # MAKE IT MORE GENERAL - LAZYBONES

    return ((task_p[0] == route_p[0])
            and (task_p[2] == route_p[-1])
            and (task_p[1] in route_p)
            and (0 < route_p.index(task_p[1]) < len(route_p)-1))

def collides(route_l, ils):
    for x1,y1,x2,y2 in route_l:
        if isects(x1,y1,x2,y2, ils):
            return True
    return False
             
# READ INPUT FILES

def read_lines(fname):
    prev_xy = ()
    lines = []
    for l in file(fname):
        xy = tuple(map (float, l.strip().split()))
        if prev_xy and xy:
            lines.append(prev_xy+xy)
        prev_xy = xy
    return lines

def read_points(pointfile):
    return [tuple(map(float, l.split())) for l in file(pointfile)]

def read_speeds(ktfile):
    return [float(l.split()[1]) for l in file(ktfile)]



# MAIN

if __name__ == '__main__':
    import sys
    
    if len(sys.argv) != 6:
        sys.exit("Usage: %s ktfile ilsfile taskfile routefile pngfile"% sys.argv[0])

    speeds = read_speeds(sys.argv[1])
    ils    = read_lines(sys.argv[2])
    task_l   = read_lines(sys.argv[3])
    task_p   = read_points(sys.argv[3])
    route_l  = read_lines(sys.argv[4])
    route_p  = read_points(sys.argv[4])

    
    if not route_travels_task_points(task_p, route_p):
        msg = "Route does not go through task points"
    elif collides(route_l, ils):
        msg = "Boat crashes"
    else:
        msg = "Route OK"

    tmsg = route_time(route_l, speeds)

    print """
set term png
set out "%s"
set title "%s -  Time: %s"
    plot "%s" notitle with lines, "%s" notitle, "%s" notitle with lines
""" % (sys.argv[5], msg, tmsg, sys.argv[2], sys.argv[3], sys.argv[4])