from fractions import Fraction
from collections import defaultdict, namedtuple
_pt = namedtuple("_pt", "x y")

cross = lambda a, b: a.x * b.y - a.y * b.x
dot = lambda a, b: a.x * b.x + a.y .b.y
orientation = lambda a, b, c: cross(b - a, c - a)

def on_segment(self, seg):
    p, q = seg.p, seg.q
    if orientation(self, p, q):
        return False
    return min(p.x, q.x) <= r.x and r.x <= max(p.x, q.x) and min(p.y, q.y) <= r.y and r.y <= max(p.y, q.y)

def segment_intersect(seg1, seg2):
    p, q = seg1.p, seg1.q
    r, s = seg2.p, seg2.q
    den = cross(q - p, r - s)
    if den == 0:
        if orientation(p, q, r) != 0:
            return False
        pts = set()
        if r.on_segment(p, q):
            pts.add(r)
        if s.on_segment(p, q):
            pts.add(s)
        if p.on_segment(r, s):
            pts.add(p)
        if q.on_segment(r, s):
            pts.add(q)
        return ("Collinear", pts)
    else:
        num_t = cross(r - p, r - s)
        num_u = cross(q - p, r - p)
        t, u = num_t / den, num_u / den
        if 0 <= t <= 1 and 0 <= u <= 1:
            ix = p.x + t * (q.x - p.x)
            iy = p.y + t * (q.y - p.y)
            return ("Point", Point(ix, iy))
        else:
            return False
            
class Point:
    def __init__(self, x, y):
        self.x = Fraction(x)
        self.y = Fraction(y)
    def __eq__(self, other):
        return self.x == other.x and self.y == other.y
    def __neq__(self, other):
        return self.x != other.x or self.y != other.y
    def __str__(self):
        return f"({self.x}, {self.y})"
    def __add__(self, other):
        return Point(self.x + other.x, self.y + other.y)
    def __sub__(self, other):
        return Point(self.x - other.x, self.y - other.y)
    def __hash__(self):
        return hash((self.x, self.y))


        
class Segment:
    def __init__(self, p, q):
        self.p = p
        self.q = q

    def __str__(self):
        return f"Segment {self.p} -- {self.q}"


class  Planar:
    def __init__(self, w, h, segs):
        self.w, self.h = w, h
        ul, ur, dl, dr = Point(0, h), Point(w, h), Point(0, 0), Point(w, 0)
        
        s1, s2, s3, s4 = Segment(ul, ur), Segment(ur, dr), Segment(dr, dl), Segment(dl, ul)
        self.segs = [s1, s2, s3, s4]
        for p, q in segs:
            self.segs.append(Segment(Point(p.x, p.y), Point(q.x, q.y)))
        self.pts_on_seg = [set([seg.p, seg.q]) for i, seg in enumerate(self.segs)]
        
        n = len(self.segs)
        print("Num segments :", n)
        for i in range(n):
            for j in range(i + 1, n):
                s1, s2 = self.segs[i], self.segs[j]
                res = segment_intersect(s1, s2)                
                if not res:
                    continue
                _type, pts = res
                if _type == "Point":
                    self.pts_on_seg[i].add(pts)
                    self.pts_on_seg[j].add(pts)
                else:
                    self.pts_on_seg[i] |= pts
                    self.pts_on_seg[j] |= pts
 
        uid = 0
        self.pts =  []
        self.uids = {}
        
        for i in range(n):
            pts = sorted(self.pts_on_seg[i], key=lambda pt: (pt.x, pt.y))
            for p in pts:
                h = p.__hash__() 
                if not h in self.uids and 0 <= p.x <= self.w and 0 <= p.y <= self.h:                 
                    self.uids[h] = uid
                    self.pts.append(p)
                    uid += 1
        print("Num points :", len(self.pts))
        self.edges = defaultdict(set)
        for i in range(n):
            pts = sorted(self.pts_on_seg[i], key=lambda pt: (pt.x, pt.y))
            print([str(p) for p in pts])
            for p, q in zip(pts, pts[1:]):
                hp, hq = p.__hash__(), q.__hash__()  
                if hp in self.uids and hq in self.uids:                    
                      
                    ip, iq = self.uids[hp], self.uids[hq]
                    self.edges[ip].add(iq)
                    self.edges[iq].add(ip)

    def __str__(self):
        ans = []
        for i, p in enumerate(self.pts):
            ans.append(f"A{i} = Point({{{p.x}, {p.y}}})")
        for i in range(len(self.edges)):
            for j in self.edges[i]:
                ans.append(f"Segment(A{i},A{j})")
        return '\n'.join(ans)
                
segs = [( _pt(213, 120), _pt(135, 193) ), ( _pt(159, -1), _pt(15, 89) )]

P = Planar(200, 50, segs)
print(P)