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:
# -*- coding: utf-8 -*-

import collections
import math

import bisect

class Vector2(collections.namedtuple("Vector2", ["x",  "y"])):

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

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

    def __mul__(self, scalar):
        return Vector2(self.x * scalar, self.y * scalar)

    def __neg__(self):
        return Vector2(-self.x, -self.y)

    def __pos__(self):
        return Vector2(+self.x, +self.y)

    def __abs__(self):  # norm
        return math.sqrt(float(self.x * self.x + self.y * self.y))

    def __truediv__(self, scalar):
        return Vector2(self.x / scalar, self.y / scalar)

    def abs2(self):
        return float(self.x * self.x + self.y * self.y)

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

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


def getDistanceSP(segment, point):
    p = point
    p1, p2 = segment
    if (p2 - p1).dot(p - p1) < 0:
        return abs(p - p1)
    if (p1 - p2).dot(p - p2) < 0:
        return abs(p - p2)
    return abs((p2 - p1).cross(p - p1)) / abs(p2 - p1)


def getDistance(s1, s2):
    a, b = s1
    c, d = s2
    if intersect(s1, s2):  # intersect
        return 0
    return min(getDistanceSP(s1, c), getDistanceSP(s1, d), getDistanceSP(s2, a), getDistanceSP(s2, b))


def ccw(p0, p1, p2):
    a = p1 - p0
    b = p2 - p0
    if a.cross(b) > 0:
        return 1  # COUNTER_CLOCKWISE
    elif a.cross(b) < 0:
        return -1  # CLOCKWISE
    elif a.dot(b) < 0:
        return 2  # ONLINE_BACK
    elif abs(a) < abs(b):
        return -2  # ONLINE_FRONT
    else:
        return 0  # ON_SEGMENT


def intersect(s1, s2):
    a, b = s1
    c, d = s2
    return ccw(a, b, c) * ccw(a, b, d) <= 0 and ccw(c, d, a) * ccw(c, d, b) <= 0


def project(l, p):
    p1, p2 = l
    base = p2 - p1
    hypo = p - p1
    return p1 + base * (hypo.dot(base) / abs(base)**2)


class Circle():
    def __init__(self, c, r):
        self.c = c
        self.r = r


def getCrossPoints(c, l):
    pr = project(l, c.c)
    p1, p2 = l
    e = (p2 - p1) / abs(p2 - p1)
    base = math.sqrt(c.r * c.r - (pr - c.c).abs2())
    return [pr + e * base, pr - e * base]


def polar(r, a):
    return Vector2(r * math.cos(a), r * math.sin(a))


def getCrossPointsCircle(c1, c2):
    base = c2.c - c1.c
    d = abs(base)
    a = math.acos((c1.r**2 + d**2 - c2.r**2) / (2 * c1.r * d))
    t = math.atan2(base.y, base.x)
    return [c1.c + polar(c1.r, t + a), c1.c + polar(c1.r, t - a)]


def contains(g, p):
    n = len(g)
    x = 0
    for i in range(n):
        a = g[i] - p
        b = g[(i + 1) % n] - p
        if a.cross(b) == 0 and a.dot(b) <= 0:
            return 1
        if a.y > b.y:
            a, b = b, a
        if a.y <= 0 and b.y > 0 and a.cross(b) > 0:
            x += 1

    if x % 2 == 1:
        return 2
    else:
        return 0


def andrewScan(s):
    u = []
    l = []
    s = sorted(s, key=lambda x: (x.x, x.y))
    if len(s) < 3:
        return s
    u.append(s[0])
    u.append(s[1])
    l.append(s[-1])
    l.append(s[-2])

    for i in range(2, len(s)):
        for n in range(len(u), 1, -1):
            if ccw(u[n - 2], u[n - 1], s[i]) != 1:
                break
            else:
                u.pop()
        u.append(s[i])

    for i in range(len(s) - 3, -1, -1):
        for n in range(len(l), 1, -1):
            if ccw(l[n - 2], l[n - 1], s[i]) != 1:
                break
            else:
                l.pop()
        l.append(s[i])

    ans = l + u[1:-1]
    ans.reverse()
    return ans

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

if __name__ == '__main__':

    n = int(input())
    EP = []
    S = []
    for i in range(n):
        a, b, c, d = map(int, input().split())
        if a == c: # y軸と平行
            EP.append(EndPoint(Vector2(a, min(b, d)), i, 0)) # bottom
            EP.append(EndPoint(Vector2(a, max(b, d)), i, 3)) # top
            S.append([Vector2(a, max(b, d)), Vector2(a, min(b, d))])
        else: # x軸と平行
            EP.append(EndPoint(Vector2(min(a, c), b), i, 1)) # left
            EP.append(EndPoint(Vector2(max(a, c), b), i, 2)) # right
            S.append([Vector2(min(a, c), b), Vector2(max(a, c), b)])
    
    EP = sorted(EP, key=lambda x: (x.p.y, x.st))
    BT = []
    cnt = 0
    for e in EP:
        if e.st == 3: # top
            indx = bisect.bisect_left(BT, e.p.x)
            BT.pop(indx)
            # BT.remove(e.p.x)
        elif e.st == 0: # bottom
            bisect.insort_left(BT, e.p.x)
        elif e.st == 1: # left
            l = bisect.bisect_left(BT, S[e.seg][0].x)
            r = bisect.bisect_right(BT, S[e.seg][1].x)
            cnt += r-l

    print(cnt)

Submission status: Accepted

Solution code:
import math

class Vector:
    def __init__(self,x,y):
        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,scalar):
        return Vector(self.x*scalar,self.y*scalar)
    def __rmul__(self, scalar):
        return Vector(self.x*scalar,self.y*scalar)
    
   
    def __repr__(self):
        return str([self.x,self.y])
        
    def norm_2(self):
        return dot(self,self)
    
    def norm(self):
        return math.sqrt(self.norm_2())
    
def v_sum(v1,v2):
    return Vector(v1.x+v2.x,v1.y+v2.y) 
def scalar_multi(k,v):
    return Vector(k*v.x,k*v.y)
def v_diff(v1,v2):
    return v_sum(v1,scalar_multi(-1,v2))
    
def dot(vector1,vector2):
    return vector1.x*vector2.x+vector1.y*vector2.y

def cross(vector1,vector2):
    return vector1.x*vector2.y-vector1.y*vector2.x


import bisect

class EndPoint(Vector):
    def __init__(self,x,y,state):
        super().__init__(x,y)
        self.state = state
        '''
        state 0 bottom
        state 1 top
        state 2 left
        state 3 right
        '''
        return
    
class Segment:
    def __init__(self,p1,p2):
        if p1.x<p2.x:
            self.p1 = p1
            self.p2 = p2
        else:
            self.p1 = p2
            self.p2 = p1
        return
    
    
def sorting(p):
    if isinstance(p,Segment):
        return p.p1.y+0.1
    else:
        if p.state == 0:
            return p.y
        elif p.state == 1:
            return p.y+0.2
    
    
    

n = int(input())
points = []
for i in range(n):
    x1,y1,x2,y2 = map(int,input().split())
    if x1 == x2:
        if y1<y2:
            points.append(EndPoint(x1,y1,0))
            points.append(EndPoint(x2,y2,1))
        else:
            points.append(EndPoint(x1,y1,1))
            points.append(EndPoint(x2,y2,0))
    else:
        if x1<x2:
            points.append(Segment(EndPoint(x1,y1,2),EndPoint(x2,y2,3)))
        else:
            points.append(Segment(EndPoint(x1,y1,3),EndPoint(x2,y2,2)))
        
points.sort(key = lambda x:sorting(x))

T = []
count = 0
for i in range(len(points)):
    if isinstance(points[i],Segment):
        left = bisect.bisect_left(T,points[i].p1.x)
        right = bisect.bisect_right(T,points[i].p2.x)
        count += right-left
    else:
        if points[i].state == 0:
            bisect.insort(T,points[i].x)
        elif points[i].state == 1:
            index=bisect.bisect_left(T,points[i].x)
            T.pop(index)

print(count)

Submission status: Accepted

Solution code:
import bisect
from collections import deque

n = int(input())
Ps = []
for i in range(n):
    x1,y1,x2,y2 = map(int,input().split())
    if x1 == x2:
        if y2 < y1:
            y1,y2 = y2,y1
        Ps.append((y1,x1,"s",0))
        Ps.append((y2,x1,"g",2))

    else:
        if x2 < x1:
            x1,x2 = x2,x1
        Ps.append((y1,x1,x2,1))
Ps.sort(key=lambda x:x[3])
Ps.sort(key=lambda x:x[0])
N = len(Ps)
ans = 0
X = deque()

for i in range(N):
    query = Ps[i]
    if query[2] == "s":
        X.insert(bisect.bisect_left(X,query[1]), query[1])
    elif query[2] == "g":
        del X[bisect.bisect_left(X,query[1])]
    else:
        ans += bisect.bisect_left(X,query[1]) - bisect.bisect_right(X,query[2])

print(-ans)

Submission status: Accepted

Solution code:

import operator
from operator import itemgetter
class SegmentTree:
    # http://tsutaj.hatenablog.com/entry/2017/03/29/204841
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size

def resolve():
    BOTTOM, HORIZONTAL, TOP = 0, 1, 2
    N = int(input())
    XY = [list(map(int, input().split())) for _ in range(N)]
    # X軸の点を列挙
    X = set(x1 for x1, y1, x2, y2 in XY) | set(x2 for x1, y1, x2, y2 in XY)
    # X軸の点を左端から順序付け
    c = {xi: i for i, xi in enumerate(sorted(X))}

    que = []
    for x1, y1, x2, y2 in XY:
        if y1 == y2:
            if x1 > x2:
                x1, x2 = x2, x1
            # 高さが同じ場合、左、右に点がある
            que.append((y1, HORIZONTAL, c[x1], c[x2]))
        else:
            if y1 > y2:
                y1, y2 = y2, y1
            x1 = c[x1]
            # 高さが違う場合、X軸は同じでY軸は高いか、低いかで場合分け
            que.append((y1, BOTTOM, x1, None))
            que.append((y2, TOP, x1, None))
    # yを下から走査するためにソート
    que.sort(key=itemgetter(0, 1))

    st = SegmentTree(len(X))
    ans = 0
    for y, action, x1, x2 in que:
        if action == BOTTOM:
            st.add(x1, 1)
        elif action == TOP:
            # 判定が終る線分なので削除
            st.add(x1, -1)
        else:
            # X軸の左右の範囲内にある線分を数える
            ans += st.get(x1, x2+1)
    print(ans)

if __name__ == '__main__':
    resolve()