Problem:
Segment Intersections: Manhattan Geometry For given $n$ segments which are parallel to X-axis or Y-axis, find the number of intersections of them. Input In the first line, the number of segments $n$ is given. In the following $n$ lines, the $i$-th segment is given by coordinates of its end points in the following format:  $x_1 \; y_1 \; x_2 \; y_2$  The coordinates are given in integers. Output Print the number of intersections in a line. Constraints  $1 \leq n \leq 100,000$  $ -1,000,000,000 \leq x_1, y_1, x_2, y_2 \leq 1,000,000,000$  Two parallel segments never overlap or touch. The number of intersections  $\leq 1,000,000$  Sample Input 1 6
2 2 2 5
1 3 5 3
4 1 4 4
5 2 7 2
6 1 6 3
6 5 6 7 Sample Output 1 3

Solution (Python):
import bisect
import sys
from typing import List, Tuple, Set


class BIT(object):
    def __init__(self, n: int) -> None:
        self.tree = [0] * (n + 1)
        self.n = n

    def add(self, i: int, v: int) -> None:
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i: int) -> int:
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l: int, h: int) -> int:
        return self._sum(h) - self._sum(l - 1)


if __name__ == "__main__":
    n = int(input())
    vx: List[Tuple[int, int, int]] = []
    x_init_set: Set[int] = set()
    for _ in range(n):
        x1, y1, x2, y2 = map(lambda x: int(x), input().split())
        if x1 == x2:
            if y1 > y2:
                y1, y2 = y2, y1
            vx.append((y1, -sys.maxsize, x1))
            vx.append((y2, sys.maxsize, x1))
            x_init_set.add(x1)
        else:
            if x1 > x2:
                x1, x2 = x2, x1
            vx.append((y1, x1, x2))
    vx.sort()

    bit = BIT(len(x_init_set))
    xs = [-sys.maxsize] + sorted(x_init_set)
    ix = {v: i for i, v in enumerate(xs)}
    ans = 0

    for y, j, x2 in vx:
        if j == -sys.maxsize:
            bit.add(ix[x2], 1)
        elif j == sys.maxsize:
            bit.add(ix[x2], -1)
        else:
            i1 = bisect.bisect_left(xs, j)
            i2 = bisect.bisect(xs, x2) - 1
            ans += bit.sum(i1, i2)

    print(ans)

Solution (Python):



from sys import stdin
from typing import Any, List, Optional

from enum import IntEnum


class EPStatus(IntEnum):
    BOTTOM = 0
    LEFT = 1
    RIGHT = 2
    TOP = 3


class Point:
    def __init__(self, x: float = 0.0, y: float = 0.0) -> None:
        self.x = x
        self.y = y

    def __repr__(self) -> str:
        return "({}, {})".format(self.x, self.y)


class Segment:
    def __init__(
        self, p1: Optional[Point] = None, p2: Optional[Point] = None
    ) -> None:
        self.p1 = Point() if p1 is None else p1
        self.p2 = Point() if p2 is None else p2

    def __repr__(self) -> str:
        return "({}, {})".format(self.p1, self.p2)


class EndPoint:
    def __init__(self, p: Point, seg: Segment, st: EPStatus):
        self.p = p
        self.seg = seg
        self.st = st

    def __lt__(self, other: "EndPoint") -> bool:
        return (
            self.st < other.st
            if self.p.y == other.p.y
            else self.p.y < other.p.y
        )


class Node:
    def __init__(
        self,
        key: Any,
        parent: Optional["Node"] = None,
        left: Optional["Node"] = None,
        right: Optional["Node"] = None,
    ) -> None:
        self.key = key
        self.parent = parent
        self.left = left
        self.right = right

    def __str__(self) -> str:
        return "({} {} {})".format(self.key, self.left, self.right)

    def minimum_child(self) -> "Node":
        x = self
        while x.left is not None:
            x = x.left
        return x

    def successor(self) -> Optional["Node"]:
        if self.right is not None:
            return self.right.minimum_child()

        x = self
        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y


class Tree:
    def __init__(self) -> None:
        self.root: Optional[Node] = None

    def __str__(self) -> str:
        return str(self.root) if self.root else "()"

    def insert(self, z: Node) -> None:
        y = None
        x = self.root

        while x is not None:
            y = x
            x = x.left if z.key < x.key else x.right

        z.parent = y
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def find(self, key: Any) -> Optional[Node]:
        x = self.root
        while x is not None and key != x.key:
            x = x.left if key < x.key else x.right
        return x

    def delete(self, z: Node) -> None:
        y = z if z.left is None or z.right is None else z.successor()
        x = y.right if y.left is None else y.left

        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        if y != z:
            z.key = y.key

    def lower_bound(self, key: Any) -> Optional[Node]:
        x = self.root
        b: Optional[Node] = None

        while x is not None:
            if key < x.key:
                if b is None or x.key < b.key:
                    b = x
                x = x.left
            elif key == x.key:
                b = x
                break
            else:
                x = x.right

        return b


def manhattanIntersection(S: List[Segment]) -> int:
    def crosses(x1: float, x2: float) -> int:
        cnt: int = 0
        node: Optional[Node] = BT.lower_bound(x1)
        while node is not None and node.key <= x2:
            cnt += 1
            node = node.successor()
        return cnt

    EP: List[EndPoint] = []

    for s in S:
        if (s.p1.y == s.p2.y and s.p1.x > s.p2.x) or (
            s.p1.x == s.p2.x and s.p1.y > s.p2.y
        ):
            s.p1, s.p2 = s.p2, s.p1

        if s.p1.y == s.p2.y:
            EP.append(EndPoint(s.p1, s, EPStatus.LEFT))
        else:
            EP.append(EndPoint(s.p1, s, EPStatus.BOTTOM))
            EP.append(EndPoint(s.p2, s, EPStatus.TOP))

    EP.sort()

    BT = Tree()
    cnt = 0

    for e in EP:
        if e.st == EPStatus.TOP:
            BT.delete(BT.find(e.p.x))
        elif e.st == EPStatus.BOTTOM:
            BT.insert(Node(e.p.x))
        elif e.st == EPStatus.LEFT:
            cnt += crosses(e.seg.p1.x, e.seg.p2.x)

    return cnt


def main() -> None:
    S = []

    n = int(stdin.readline())
    for i in range(n):
        x1, y1, x2, y2 = [int(x) for x in stdin.readline().split()]
        S.append(Segment(Point(x1, y1), Point(x2, y2)))

    print(manhattanIntersection(S))


main()

Solution (Python):
from sys import stdin
import math

class Vector:
    def __init__(self, x=None, y=None):
        self.x = x
        self.y = y

    def __add__(self, other):
        return Vector(self.x + other.x, self.y + other.y)

    def __sub__(self, other):
        return Vector(self.x - other.x, self.y - other.y)

    
    def __mul__(self, k):
        return Vector(self.x * k, self.y * k)

    def __truediv__(self, k):
        return Vector(self.x / k, self.y / k)

    def __gt__(self, other):
        return self.x > other.x and self.y > other.yb

    def __lt__(self, other):
        return self.x < other.x and self.y < other.yb

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

    def dot(self, other):
        return self.x * other.x + self.y * other.y

    
    def cross(self, other):
        return self.x * other.y - self.y * other.x

    def norm(self):
        return self.x * self.x + self.y * self.y

    def abs(self):
        return math.sqrt(self.norm())

    def rotate(self, theta):
        return Vector(self.x * math.cos(theta)
                               - self.y * math.sin(theta),
                               self.x * math.sin(theta)
                               + self.y * math.cos(theta))

class Point(Vector):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

class Segment:
    def __init__(self, p1=Point(0, 0), p2=Point(1, 1)):
        self.p1 = p1
        self.p2 = p2

class Line(Segment):
    def __init__(self, *args, **kargs):
        return super().__init__(*args, **kargs)

class EndPoint:
    def __init__(self, p1, p2):
        self.point = p1
        self.otherend = p2
        if p1.x == p2.x:
            if p1.y > p2.y:
                self.type = 2 
            else:
                self.type = 0 
        elif p1.y == p2.y:
            if p1.x < p2.x:
                self.type = 1 
            else:
                self.type = 3 

def manhattan_geometry(S):
    end_points = []
    count = 0
    for i in S:
        ep1 = EndPoint(i.p1, i.p2)
        ep2 = EndPoint(i.p2, i.p1)
        if ep1.type != 3:
            end_points.append(ep1)
        if ep2.type != 3:
            end_points.append(ep2)

    end_points.sort(key=lambda ep: (ep.point.y, ep.type, ep.point.x))
    T = set({})
    for i in end_points:
        if i.type == 2: 
            T.remove(i.point.x)
        if i.type == 0: 
            T.add(i.point.x)
        if i.type == 1: 
            inclueded_x = {j for j in T if j >= i.point.x and j <= i.otherend.x}
            count = count + len(inclueded_x)
    return count

def read_segments(n):
    S = []
    for _ in range(n):
        line = stdin.readline().strip().split()
        p0 = Vector(int(line[0]), int(line[1]))
        p1 = Vector(int(line[2]), int(line[3]))
        s = Segment(p0, p1)
        S.append(s)
    return S

def __main():
    n = int(input())
    S = read_segments(n)
    count = manhattan_geometry(S)
    print(count)

if __name__ == '__main__':
    __main()

Solution (Python):



from enum import IntEnum


class Action(IntEnum):
    ADD = 1
    SEARCH = 2
    REMOVE = 3


class Color(IntEnum):
    BLACK = 0
    RED = 1

    @staticmethod
    def flip(c):
        return [Color.RED, Color.BLACK][c.value]


class Node:
    __slots__ = ('value', 'left', 'right', 'color', 'valid')

    def __init__(self, value):
        self.value = value
        self.left = Leaf
        self.right = Leaf
        self.color = Color.RED
        self.valid = True

    def flip_color(self):
        self.color = Color.flip(self.color)

    def is_red(self):
        return self.color == Color.RED

    def __str__(self):
        return ('(' + str(self.left) + ', '
                + str(self.value) + ', ' + str(self.right) + ')')


class LeafNode(Node):
    def __init__(self):
        self.value = None
        self.left = None
        self.right = None
        self.color = None
        self.valid = False

    def flip_color(self):
        pass

    def is_red(self):
        return False

    def __str__(self):
        return 'Leaf'


Leaf = LeafNode()


class RedBlackBST:
    def __init__(self):
        self.root = Leaf

    def add(self, value):
        def _add(node):
            if node is Leaf:
                node = Node(value)
            if node.value > value:
                node.left = _add(node.left)
            elif node.value < value:
                node.right = _add(node.right)
            else:
                if not node.valid:
                    node.valid = True

            node = self._balance(node)
            return node

        self.root = _add(self.root)
        self.root.color = Color.BLACK

    def _balance(self, node):
        if node.right.is_red() and not node.left.is_red():
            node = self._rotate_left(node)
        if node.left.is_red() and node.left.left.is_red():
            node = self._rotate_right(node)
        if node.left.is_red() and node.right.is_red():
            node = self._flip_colors(node)
        return node

    def _rotate_left(self, node):
        x = node.right
        node.right = x.left
        x.left = node
        x.color = node.color
        node.color = Color.RED
        return x

    def _rotate_right(self, node):
        x = node.left
        node.left = x.right
        x.right = node
        x.color = node.color
        node.color = Color.RED
        return x

    def _flip_colors(self, node):
        node.flip_color()
        node.left.flip_color()
        node.right.flip_color()
        return node

    def remove(self, value):
        def _remove(node):
            if node is Leaf:
                return
            if node.value > value:
                _remove(node.left)
            elif node.value < value:
                _remove(node.right)
            else:
                node.valid = False

        _remove(self.root)

    def count(self, min_, max_):
        def _range(node):
            if node is Leaf:
                return 0

            if node.value > max_:
                return _range(node.left)
            elif node.value < min_:
                return _range(node.right)
            else:
                count = _range(node.left) + _range(node.right)
                if node.valid:
                    count += 1
                return count

        return _range(self.root)

    def __str__(self):
        return str(self.root)


def count_intersections(segments):
    segments.sort()
    tree = RedBlackBST()
    count = 0
    for seg in segments:
        x, action, y = seg
        if action == Action.SEARCH:
            count += tree.count(*y)
        elif action == Action.ADD:
            tree.add(y)
        elif action == Action.REMOVE:
            tree.remove(y)

    return count


def run():
    n = int(input())
    segs = []

    for _ in range(n):
        x1, y1, x2, y2 = [int(i) for i in input().split()]
        if x1 > x2 or y1 > y2:
            x1, x2 = x2, x1
            y1, y2 = y2, y1
        if x1 == x2:
            segs.append((x1, Action.SEARCH, (y1, y2)))
        else:
            segs.append((x1, Action.ADD, y1))
            segs.append((x2, Action.REMOVE, y2))

    print(count_intersections(segs))


if __name__ == '__main__':
    run()

Solution (Python):
import sys
import bisect

def main():
    num_segments = int(input())
    events = [None] * num_segments * 2
    num_events = 0

    lines = sys.stdin.readlines()
    for line in lines:
        pt1_x, pt1_y, pt2_x, pt2_y = map(int, line.split())
        if pt1_x == pt2_x:
            if pt1_y > pt2_y:
                pt1_y, pt2_y = pt2_y, pt1_y
            events[num_events] = (pt1_y, pt1_x, 0)
            num_events += 1
            events[num_events] = (pt2_y, pt2_x, 2)
            num_events += 1
        elif pt1_y == pt2_y:
            if pt1_x > pt2_x:
                pt1_x, pt2_x = pt2_x, pt1_x
            events[num_events] = (pt1_y, (pt1_x, pt2_x), 1)
            num_events += 1
        else:
            raise AssertionError

    events = events[:num_events]
    events.sort(key=lambda x: (x[0], x[2]))

    cross_count = 0
    vertical = []
    for event in events:
        if event[2] == 0:
            bisect.insort_left(vertical, event[1])
        elif event[2] == 2:
            i = bisect.bisect_left(vertical, event[1])
            del vertical[i]
        else:   
            left_x, right_x = event[1][0], event[1][1]
            for v_x in vertical:
                if left_x <= v_x <= right_x:
                    cross_count += 1
    print(cross_count)


main()

Solution (Python):
import sys
file_input = sys.stdin
n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0

for line in file_input:
  x1, y1, x2, y2 = map(int, line.split())
  if x1 == x2:
    if y1 < y2:
      EP.append((y1, l, x1))
      EP.append((y2, u, x1))
    else:
      EP.append((y1, u, x1))
      EP.append((y2, l, x1))
    vs_x.add(x1)
  else:
    if x1 < x2:
      EP.append((y1, x1, x2))
    else:
      EP.append((y1, x2, x1))
    h_num += 1

class BinaryIndexedTree:
  def __init__(self, n):
    self.data = [0] *(n+1)
    self.num = n

  def switch(self, i, d):
    while  i <= self.num:
      self.data[i] += d
      i += i & -i

  def sum(self, i):
    s = 0
    while  i:
      s += self.data[i]
      i -= i & -i
    return s

  def seg_sum(self, a, b):
    return self.sum(b) - self.sum(a- 1)

import bisect

EP.sort()
BIT = BinaryIndexedTree(len(vs_x))
vs_x = [l] + sorted(vs_x)
d_vs_x = {e:i for i, e in enumerate(vs_x)}

cnt = 0

for p in EP:
  e = p[1]
  if e== l:
    BIT.switch(d_vs_x[p[2]], 1)
  elif e==u:
    BIT.switch(d_vs_x[p[2]], -1)
  else:
    l_x = bisect.bisect_left(vs_x, e)
    r_x = bisect.bisect(vs_x, p[2]) -1
    cnt += BIT.seg_sum(l_x,r_x)
    h_num -= 1
  if h_num ==0:
    break
print(cnt)