Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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



Sample input:
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:
3

Submission status: Accepted

Solution code:
#! /usr/bin/env python3
# -*- coding: utf-8 -*-

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()

Submission status: Accepted

Solution code:
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)

    # can't  apply "number * Vector" but "Vector * number"
    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

    # usually cross operation return Vector but it returns scalor
    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 # 'Vertical Top'
            else:
                self.type = 0 # 'Vertical Bottom'
        elif p1.y == p2.y:
            if p1.x < p2.x:
                self.type = 1 # 'Horizontal Left'
            else:
                self.type = 3 # 'Horizontal Right'

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: # 'Vertical Top'
            T.remove(i.point.x)
        if i.type == 0: # 'Vertical Bottom'
            T.add(i.point.x)
        if i.type == 1: # 'Horizontal Left'
            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()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# CGL_6_A: Segment Set - Segment Intersections: Manhattan Geometry

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()

Submission status: Accepted

Solution code:
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:   # horizontal
            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()

Submission status: Accepted

Solution code:
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)


#一言：平面操作でユーグリッド空間上の線分交点を求める
#処理の流れ：入力された線分端点をyを基準に昇順にリストに入れる。→順番に取り出す。→下恥ならBSTに挿入。・上端ならBSTから削除。入れたものがx軸と交差したらそこで探索を開始する。
#計算量：O(nlogn+k)（二分木探索の計算量nlogn+交点k）

Submission status: Runtime Error

Solution code:
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.RED

  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.right)
      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


n=int(input())
segs=[]

for i in range(n):
  x1,y1,x2,y2=map(int,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))

Submission status: Runtime Error

Solution code:
lass AvlTree(BinarySearchTree):
    '''An extension t the BinarySearchTree data structure which 
    strives to keep itself balanced '''

    def _put(self,key,val,currentNode):
        if key < currentNode.key:
            if current.Node.hasLeftChild():
                self._put(key,val,currentNode.leftChild)
            else:
                currentNode.leftChild = TreeNode(key,val,parent=currentNode)
                self.updateBalance(currentNode.leftChile)
        else:
            if currentNode.hasRightChild():
                self._put(key,val,currentNode.rightChild)
            else:
                currentNode.rightChild = TreeNode(key,val,parent=currentNode)
                self.updateBalance(currentNode.rightChild)

    def updateBalance(self,node):
        if node.balanceFactor > 1 or node.balanceFactor < -1:
            self.rebalance(node)
            return
        if node.parent != None:
            if node.isLeftChild():
                node.parent.balancefactor += 1
            elif node.isRightChild():
                node.parent.balanceFactor -= 1

            if node.parent.balanceFactor != 0:
                self.updateBalance(node.parent)

    def rotateLeft(self,rotRoot):
        newRoot = rotRoot.rightChild
        rotRoot.rightChild = newRoot.leftChild
        if newRoot.leftChild != None:
            newRoot.leftChild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isLeftChild():
                rotRoot.parent.leftChild = newRoot
            else:
                rotRoot.parent.rightChild = newRoot
        newRoot.leftChild = rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(
            newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.blanceFactor + 1 + max(
            rotRoot.balanceFactor, 0)

    def rotateRight(self,rotRoot):
        newRoot = rotRoot.leftChild
        rotRoot.leftChild = newRoot.rightChild
        if newRoot.rightChild != None:
            newRoot.rightChild.parent = rotRoot
        newRoot.parent = rotRoot.parent
        if rotRoot.isRoot():
            self.root = newRoot
        else:
            if rotRoot.isRightChild():
                rotRoot.parent.rightChild = newRoot   
                # leftchild??????
        newRoot.rightChild = rotRoot
        rotRoot.parent = newRoot
        rotRoot.balanceFactor = rotRoot.balanceFactor + 1 - min(
            newRoot.balanceFactor, 0)
        newRoot.balanceFactor = newRoot.balanceFactor + 1 + max(
            rotRoot.balanceFactor, 0)

    def rebalance(self,node):
        if node.balanceFactor < 0:
            if node.rightChild.balanceFactor > 0:
                self.rotateRight(node.rightChild)
                self.rotateLeft(node)
            else:
                self.rotateLeft(node)
        elif node.balanceFactor > 0:
            if node.leftChild.balanceFactor < 0:
                self.rotateLeft(node.leftchilc)
                self.rotateRight(node)
            else:
                self.rotateRight(node)