from collections import namedtuple
from blist import blist, sortedlist     # pip install blist

Point = namedtuple('Point', 'x y')

Segment = namedtuple('Segment', 'p q')
Segment.from_floats = lambda x0, y0, x1, y1: Segment.from_points(Point(x0, y0), Point(x1, y1))
Segment.from_points = lambda p, q: Segment(*sorted([p, q]))
Segment.ccw = lambda self, p: Triangle(p, *self).ccw()
Segment.cut = lambda self, other: self.ccw(other.p) ^ self.ccw(other.q)
Segment.det = lambda self: self.p.x*self.q.y - self.p.y*self.q.x
Segment.dx = lambda self: self.p.x - self.q.x
Segment.dy = lambda self: self.p.y - self.q.y

Pair = namedtuple('Pair', 's t')
Pair.from_segments = lambda s, t: Pair(*sorted([s, t]))
Pair.denominator = lambda self: self.s.dx()*self.t.dy() - self.s.dy()*self.t.dx()
Pair.is_intersect = lambda self: self.s.cut(self.t) and self.t.cut(self.s)
Pair.intersect_coord = ( lambda self:
          None if not self.is_intersect() else
          Point( (self.s.det()*self.t.dx() - self.s.dx()*self.t.det()) / self.denominator(),
                 (self.s.det()*self.t.dy() - self.s.dy()*self.t.det()) / self.denominator() ))

Triangle = namedtuple('Triangle', 'u v w')
Triangle.ccw = lambda self: round(self.det(), 9) > 0
Triangle.det = lambda self: ( self.u.x*self.v.y - self.u.y*self.v.x +
                              self.v.x*self.w.y - self.v.y*self.w.x +
                              self.w.x*self.u.y - self.w.y*self.u.x )

AddEvent = namedtuple('AddEvent', 'p s t')      # dummy 3rd attr
AddEvent.from_segment = lambda s: AddEvent(s.p, s, s)

DelEvent = namedtuple('DelEvent', 'p s t')      # dummy 3rd attr
DelEvent.from_segment = lambda s: DelEvent(s.q, s, s)

IntersectEvent = namedtuple('IntersectEvent', 'p s t')
IntersectEvent.from_segments = lambda s, t: IntersectEvent.from_pair(Pair.from_segments(s, t))
IntersectEvent.from_pair = lambda ps: IntersectEvent(ps.intersect_coord(), *ps)


def init_events(segments):
    events = sortedlist()
    for s in segments:
        events.add(AddEvent.from_segment(s))
        events.add(DelEvent.from_segment(s))
    return events

def add_intersect_event(i, j, status, events):
    if 0 <= i < len(status) and 0 <= j < len(status):
        intersection = IntersectEvent.from_segments(status[i], status[j])
        if ( intersection.p is not None
                and intersection not in events
                and events[0].p <= intersection.p <= events[-1].p ):
            events.add(intersection)

def ccw_bin_search(event, status):
    lo = 0
    hi = len(status)
    while lo < hi:
        i = (lo+hi) // 2
        if status[i].ccw(event.p):
            lo = i + 1
        else:
            hi = i
    return lo

def sweep(segments):
    intersections = set()
    status = blist()
    events = init_events(segments)
    while events:
        i = ccw_bin_search(events[0], status)
        if isinstance(events[0], AddEvent):
            status.insert(i, events[0].s)
            add_intersect_event(i, i-1, status, events)
            add_intersect_event(i, i+1, status, events)
        elif isinstance(events[0], DelEvent):
            del status[i]
            add_intersect_event(i-1, i, status, events)
        else:
            intersections.add(Pair(events[0].s, events[0].t))
            status[i], status[i+1] = status[i+1], status[i]
            add_intersect_event(i-1, i-0, status, events)
            add_intersect_event(i+1, i+2, status, events)
        del events[0]
    return intersections