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: Wrong Answer

Solution code:
from sys import stdin
from operator import itemgetter
readline = stdin.readline




VERTICAL_LOW, HORIZONTAL, VERTICAL_HIGH = 0, 1, 2

import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query([self.table[2 * i], self.table[2 * i + 1]])

    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def update(self, i, x):
        i += self.offset
        self.table[i] = x
        while 1 < i:
            i >>= 1
            self.table[i] = self.query([self.table[2 * i], self.table[2 * i + 1]])

def main():
    n = int(readline())
    p = [list(map(int, readline().split())) for _ in range(n)]
    x = set(x1 for x1, y1, x2, y2 in p) | set(x2 for x1, y1, x2, y2 in p)
    c = {xi:i for i, xi in enumerate(x)}
    que = []
    for x1, y1, x2, y2 in p:
        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]
            que.append((y1, VERTICAL_LOW, x1, None))
            que.append((y2, VERTICAL_HIGH, x1, None))
    que.sort(key=itemgetter(0, 1))

    vertical_info = segment_tree([0] * len(x), sum, default=0)

    intersection = 0
    for y1, action, x1, x2 in que:
        if action == VERTICAL_LOW:
            vertical_info.update(x1, 1)
        elif action == HORIZONTAL:
            intersection += vertical_info.find(x1, x2)
        else:
            vertical_info.update(x1, 0)
    print(intersection)
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from operator import itemgetter
readline = stdin.readline



VERTICAL_LOW, HORIZONTAL, VERTICAL_HIGH = 2, 1, 0


import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, dat, query, default=0):
        self.offset = 2 ** math.ceil(math.log(len(dat), 2))
        self.table = [default] * self.offset + dat + [default] * (self.offset - len(dat))
        self.query = query
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.query([self.table[2 * i], self.table[2 * i + 1]])

    # [l, r] closed-interval
    def find(self, l, r):
        return self.query(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def update(self, i, x):
        i += self.offset
        self.table[i] = x
        while 1 < i:
            i >>= 1
            self.table[i] = self.query([self.table[2 * i], self.table[2 * i + 1]])

def main():
    n = int(readline())
    p = [list(map(int, readline().split())) for _ in range(n)]
    x = set(x1 for x1, y1, x2, y2 in p) | set(x2 for x1, y1, x2, y2 in p)
    c = {xi:i for i, xi in enumerate(x)}
    que = []
    for x1, y1, x2, y2 in p:
        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]
            que.append((y1, VERTICAL_LOW, x1, None))
            que.append((y2, VERTICAL_HIGH, x1, None))
    que.sort(key=itemgetter(0, 1))

    vertical_info = segment_tree([0] * len(x), sum, default=0)

    intersection = 0
    for y1, action, x1, x2 in que:
        if action == VERTICAL_LOW:
            vertical_info.update(x1, 1)
        elif action == HORIZONTAL:
            intersection += vertical_info.find(x1 + 1, x2 - 1)
        else:
            vertical_info.update(x1, 0)
    print(intersection)
main()

Submission status: Wrong Answer

Solution code:
from sys import stdin
from operator import itemgetter
readline = stdin.readline



VERTICAL_LOW, HORIZONTAL, VERTICAL_HIGH = 0, 1, 2

# TODO:????????????????????£
# TODO:?????¶??????
import math
class segment_tree:
    
    # self.table is 1-indexed
    # math.log2 not implemented 3.2.3
    def __init__(self, size):
        self.offset = 2 ** math.ceil(math.log(size, 2))
        self.table = [0] * self.offset * 2
        for i in reversed(range(1, self.offset)):
            self.table[i] = self.table[2 * i] + self.table[2 * i + 1]

    # [l, r] closed-interval
    def sum(self, l, r):
        return sum(self.__range(l,r))

    def __range(self, l, r):
        l += self.offset
        r += self.offset
        while l <= r:
            if l & 1:
                yield self.table[l]
                l += 1
            l >>= 1
            if r & 1 == 0:
                yield self.table[r]
                r -= 1
            r >>= 1
        
    def add(self, i, x):
        i += self.offset
        self.table[i] += x
        while 1 < i:
            i >>= 1
            self.table[i] = self.table[2 * i] + self.table[2 * i + 1]

def main():
    n = int(readline())
    p = [list(map(int, readline().split())) for _ in range(n)]
    x = set(x1 for x1, y1, x2, y2 in p) | set(x2 for x1, y1, x2, y2 in p)
    c = {xi:i for i, xi in enumerate(x)}
    que = []
    for x1, y1, x2, y2 in p:
        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]
            que.append((y1, VERTICAL_LOW, x1, None))
            que.append((y2, VERTICAL_HIGH, x1, None))
    que.sort(key=itemgetter(0, 1))

    vertical_info = segment_tree(len(x))

    intersection = 0
    for y1, action, x1, x2 in que:
        if action == VERTICAL_LOW:
            vertical_info.add(x1, 1)
        elif action == HORIZONTAL:
            intersection += vertical_info.sum(x1, x2)
        else:
            vertical_info.add(x1, -1)
    print(intersection)
main()

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = input()

data = [0]*(n+1)
def get(i):
    r = 0
    while i>0:
        r += data[i]
        i -= i & -i
    return r
def add(i, x):
    while i <= n:
        data[i] += x
        i += i & -i

H = []
V = []
s = set()
for i in xrange(n):
    x1, y1, x2, y2 = map(int, raw_input().split())
    if x1 == x2:
        V.append((x1, y1, y2))
    else:
        H.append((x1, y1, 1))
        H.append((x2+1, y2, -1))
        s.add(y1)
ys = sorted(s)
ymap = {e: i for i, e in enumerate(ys)}.__getitem__
V.sort(); H.sort()

ans = 0
idx_h = 0; hn = len(H)
for x, y1, y2 in V:
    while idx_h < hn and H[idx_h][0] <= x:
        add(ymap(H[idx_h][1])+1, H[idx_h][2])
        idx_h += 1
    idx_l = bisect(ys, y1)
    idx_r = bisect(ys, y2+1)
    ans += get(idx_r) - get(idx_l)
print ans

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = input()

data = [0]*(n+1)
def get(i):
    r = 0
    while i>0:
        r += data[i]
        i -= i & -i
    return r
def add(i, x):
    while i <= n:
        data[i] += x
        i += i & -i

H = []
V = []
s = set()
for i in xrange(n):
    x1, y1, x2, y2 = map(int, raw_input().split())
    if x1 == x2:
        if y1 > y2: y1, y2 = y2, y1
        V.append((x1, y1, y2))
    else:
        if x1 > x2: x1, x2 = x2, x1
        H.append((x1, y1, 1))
        H.append((x2+1, y1, -1))
        s.add(y1)
ys = sorted(s)
ymap = {e: i for i, e in enumerate(ys)}.__getitem__
V.sort(); H.sort()

ans = 0
idx_h = 0; hn = len(H)
for x, y1, y2 in V:
    while idx_h < hn and H[idx_h][0] <= x:
        add(ymap(H[idx_h][1])+1, H[idx_h][2])
        idx_h += 1
    idx_l = bisect(ys, y1)
    idx_r = bisect(ys, y2+1)
    ans += get(idx_r) - get(idx_l)
print ans

Submission status: Wrong Answer

Solution code:
from bisect import bisect
n = input()

data = [0]*(n+1)
def get(i):
    r = 0
    while i>0:
        r += data[i]
        i -= i & -i
    return r
def add(i, x):
    while i <= n:
        data[i] += x
        i += i & -i

H = []
V = []
s = set()
for i in xrange(n):
    x1, y1, x2, y2 = map(int, raw_input().split())
    if x1 == x2:
        if y1 > y2: y1, y2 = y2, y1
        V.append((x1, y1, y2))
    else:
        if x1 > x2: x1, x2 = x2, x1
        H.append((x1, y1, 1))
        H.append((x2+1, y1, -1))
        s.add(y1)
ys = sorted(s)
ymap = {e: i for i, e in enumerate(ys)}.__getitem__
V.sort(); H.sort()

ans = 0
idx_h = 0; hn = len(H)
for x, y1, y2 in V:
    while idx_h < hn and H[idx_h][0] <= x:
        add(ymap(H[idx_h][1])+1, H[idx_h][2])
        idx_h += 1
    idx_l = bisect(ys, y1)-1
    idx_r = bisect(ys, y2+1)
    ans += get(idx_r) - get(idx_l)
print ans

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2]: vertical; True / horizontal; False
    # point[3]: upper or right end; True / lower or left end; False
    if y1 < y2:
        p1 = (x1, y1, True, False)
        p2 = (x2, y2, True, True)
    elif y1 > y2:
        p1 = (x1, y1, True, True)
        p2 = (x2, y2, True, False)
    elif x1 < x2:
        p1 = (x1, y1, False, False)
        p2 = (x2, y2, False, True)
    else:
        p1 = (x1, y1, False, True)
        p2 = (x2, y2, False, False)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        if p[2]:
            if p[3]:
                T.remove(p[0])
                if flag:
                    cnt += 1
            else:
                bisect.insort(T, p[0])
        else:
            if p[3]:
                cnt += bisect.bisect(T, p[0]) - left_end
                flag = False
            else:
                left_end = bisect.bisect(T, p[0])
                flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

Submission status: Wrong Answer

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2]: 1; left, 2; lower, 3; upper, 4; right
    if y1 < y2:
        p1 = (x1, y1, 2)
        p2 = (x2, y2, 3)
    elif y1 > y2:
        p1 = (x1, y1, 3)
        p2 = (x2, y2, 2)
    elif x1 < x2:
        p1 = (x1, y1, 1)
        p2 = (x2, y2, 4)
    else:
        p1 = (x1, y1, 4)
        p2 = (x2, y2, 1)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0], p[2]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        position = p[2]
        if position == 3:
            T.remove(p[0])
            if flag:
                cnt += 1
        elif position == 2:
            bisect.insort(T, p[0])
        elif position == 4:
            cnt += bisect.bisect(T, p[0]) - left_end
            flag = False
        else:
            left_end = bisect.bisect(T, p[0])
            flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

Submission status: Wrong Answer

Solution code:
import bisect

n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0
cache = {}

for x, y1, y2 in vx:
    y2 += 1
    if y1 not in cache:
        it1 = cache[y1] = bisect.bisect(vy, (y1, x))
    else:
        it1 = cache[y1]
    if y2 not in cache:
        it2 = cache[y2] = bisect.bisect(vy, (y2,))
    else:
        it2 = cache[y2]
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)

Submission status: Wrong Answer

Solution code:
import bisect


def memoize(f):
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]

    return func


@memoize
def get_bisect(y):
    return bisect.bisect(vy, y)


n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0
neg_inf = float('-inf')

for x, y1, y2 in vx:
    it1, it2 = get_bisect((y1, x)), get_bisect((y2 + 1,))
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import bisect
readline = sys.stdin.readline
n = int(readline())
EP = []
l = -1000000001
u = 1000000001
vs_x = set()
h_num = 0
for _ in [0] * n:
    x1, y1, x2, y2 = (map(int, readline().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:
    __slots__ = ('data', 'num')
    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 sum(self.data[:b]) - sum(self.data[:a - 1])
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)

Submission status: Wrong Answer

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, 3)) # top
            EP.append(EndPoint(Vector2(a, max(b, d)), i, 0)) # bottom
            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 == 0:
            BT.remove(e.p.x)
        elif e.st == 3:
            bisect.insort_left(BT, e.p.x)
        elif e.st == 1:
            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: Wrong Answer

Solution code:
import bisect
import copy


EPS=10**(-10)
       
class Point():
    def __init__(self,x=None,y=None):
        self.x=x
        self.y=y
    def __lt__(self, value):
        if self.x!=value.x:
            return self.x<value.x
        else:
            return self.y<value.y
  
    def __eq__(self,value):
        cmp= abs(self.x-value.x)<EPS and abs(self.y-value.y)<EPS   
        return cmp
    
class Segment():
    def __init__(self,p1=Point(0,0),p2=Point(0,0)):
        self.p1=p1
        self.p2=p2
    
BOTTOM =0
LEFT=1 
RIGHT =2
TOP=3 
class EndPoint():
    def __init__(self,p=None,seg=None,st=None):
        self.p=p
        self.seg=seg
        self.st=st
    def __lt__(self, value):
        if self.p.y==value.p.y:
            return self.st<value.st
        return self.p.y<value.p.y


    

#线段相交问题，曼哈顿几何
def manhattanIntersection(S):
    
    n =len(S)
    global EP

    #按照端点的y坐标升序排序
    EP.sort()


    BT=[]            # 二叉搜索树
    #BT.insert(10000000001)# 设置标记
    cnt = 0

    for i in range(2*n):
        if EP[i].st==TOP:
            idx=bisect.bisect_left(BT,EP[i].p.x)
            if idx>=0 and idx< len(EP):
                BT.pop(idx)
            #BT.erase(EP[i].p.x) #删除上端点
        elif (EP[i].st == BOTTOM):
            bisect.insort_left(BT,EP[i].p.x)
            #BT.insert(EP[i].p.x)
        elif (EP[i].st == LEFT):
            idxb=bisect.bisect_left(BT,S[EP[i].seg].p1.x)
            idxe=bisect.bisect_left(BT,S[EP[i].seg].p2.x)
            
            #set<int>::iterator b = BT.lower_bound(S[EP[i].seg].p1.x);
            #set<int>::iterator e = BT.upper_bound(S[EP[i].seg].p2.x);
            
    #加上b到e距离
            cnt +=abs(idxe-idxb)  # distance(b, e);
    
    return cnt



n=int(input())
EP=[ None for i in range(2*n)]
S=[]
seglist=[]
k=0
for i in range(n):
    seg=Segment()
    ss=[int(x) for x in input().split()]
    seg.p1.x=ss[0]
    seg.p1.y=ss[1]
    seg.p2.x=ss[2]
    seg.p2.y=ss[3]
    copy.deepcopy(seg)
    seglist.append(copy.deepcopy(seg))
    
    seg=seglist[i]
    
    if seg.p1.y==seg.p2.y:
        if seg.p1.x>seg.p2.x:
            seg.p1,seg.p2=seg.p2,seg.p1
    elif seg.p1.y>seg.p2.y:
        seg.p1,seg.p2=seg.p2,seg.p1


        #将水平线段添加到端点列表
    if (seg.p1.y == seg.p2.y) :
        EP[k] = EndPoint(seg.p1, i, LEFT)
        k+=1
        EP[k] = EndPoint(seg.p2, i, RIGHT)
        k+=1
        
    else: # 将垂直线段添加到端点列表
          EP[k] = EndPoint(seg.p1, i, BOTTOM)
          k+=1
          EP[k] = EndPoint(seg.p2, i, TOP)
          k+=1
                 
    S.append(seg)
    

print("%d"%(manhattanIntersection(S)))

Submission status: Time Limit Exceeded

Solution code:
#線分交差問題

import bisect

class BIT:
    def __init__(self, n):
        self.tree = [0]*(n+1)
        self.n = n
    
    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i
        
    
    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret
    
    def sum(self, l, h):
        return self._sum(h) - self._sum(l-1)
    
n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'),x1))
        vx.append((y2, float('inf'),x2))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2],1)
    elif j == float('inf'):
        bit.add(xs.index(x2), -1)
    else:
        l = bisect.bisect_left(xs, j)
        r = bisect.bisect(xs, x2) - 1
        ans += bit.sum(l, r)
        
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    # point[2]: 1; left, 2; lower, 3; upper, 4; right
    if y1 < y2:
        p1 = (x1, y1, 2)
        p2 = (x2, y2, 3)
    elif y1 > y2:
        p1 = (x1, y1, 3)
        p2 = (x2, y2, 2)
    elif x1 < x2:
        p1 = (x1, y1, 1)
        p2 = (x2, y2, 4)
    else:
        p1 = (x1, y1, 4)
        p2 = (x2, y2, 1)
    EP += [p1, p2]

# Sweep function
import bisect

def manhattan_intersection(point_list):
    point_list.sort(key = lambda p: (p[1], p[0], p[2]))
    T = []
    cnt = 0
    flag = False
    for p in point_list:
        position = p[2]
        if position == 3:
            T.remove(p[0])
            if flag:
                cnt += 1
        elif position == 2:
            bisect.insort(T, p[0])
        elif position == 4:
            cnt += bisect.bisect(T, p[0]) - left_end
            flag = False
        else:
            left_end = bisect.bisect_left(T, p[0])
            flag = True
    print(cnt)

# Output
manhattan_intersection(EP)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1 = bisect.bisect(vy, (y1, float('-inf')))
    it2 = bisect.bisect(vy, (y2 + 1, float('-inf')))
    for y, x1, x2 in vy[it1:it2]:
        if x1 <= x <= x2:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def memoize(f):
    cache = {}

    def func(x):
        if x not in cache:
            cache[x] = f(x)
        return cache[x]

    return func


@memoize
def get_bisect(y):
    return bisect.bisect(vy, (y, float('-inf')))


n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1, it2 = get_bisect(y1), get_bisect(y2 + 1)
    for y, x1, x2 in vy[it1:it2]:
        if x1 <= x <= x2:
            ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect


def memoize(f):
    cache = {}

    def func(x):
        if x not in cache:
            ret = cache[x] = f(x)
            return ret
        return cache[x]

    return func


@memoize
def get_bisect(y):
    return bisect.bisect(vy, (y, float('-inf')))


n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1, it2 = get_bisect(y1), get_bisect(y2 + 1)
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect

n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0
cache = {}

for x, y1, y2 in vx:
    y2 += 1
    if y1 not in cache:
        it1 = cache[y1] = bisect.bisect(vy, (y1,))
    else:
        it1 = cache[y1]
    if y2 not in cache:
        it2 = cache[y2] = bisect.bisect(vy, (y2,))
    else:
        it2 = cache[y2]
    ans += sum(x1 <= x <= x2 for y, x1, x2 in vy[it1:it2])

print(ans)