Count The Rectangles (Codeforces 1194E)
Tags: Others, geometry

There are $$$n$$$ segments drawn on a plane; the $$$i$$$-th segment connects two points ($$$x_{i, 1}$$$, $$$y_{i, 1}$$$) and ($$$x_{i, 2}$$$, $$$y_{i, 2}$$$). Each segment is non-degenerate, and is either horizontal or vertical — formally, for every $$$i \in [1, n]$$$ either $$$x_{i, 1} = x_{i, 2}$$$ or $$$y_{i, 1} = y_{i, 2}$$$ (but only one of these conditions holds). Only segments of different types may intersect: no pair of horizontal segments shares any common points, and no pair of vertical segments shares any common points.We say that four segments having indices $$$h_1$$$, $$$h_2$$$, $$$v_1$$$ and $$$v_2$$$ such that $$$h_1 < h_2$$$ and $$$v_1 < v_2$$$ form a rectangle if the following conditions hold:  segments $$$h_1$$$ and $$$h_2$$$ are horizontal;  segments $$$v_1$$$ and $$$v_2$$$ are vertical;  segment $$$h_1$$$ intersects with segment $$$v_1$$$;  segment $$$h_2$$$ intersects with segment $$$v_1$$$;  segment $$$h_1$$$ intersects with segment $$$v_2$$$;  segment $$$h_2$$$ intersects with segment $$$v_2$$$. Please calculate the number of ways to choose four segments so they form a rectangle. Note that the conditions $$$h_1 < h_2$$$ and $$$v_1 < v_2$$$ should hold.

Input: The first line contains one integer $$$n$$$ ($$$1 \le n \le 5000$$$) — the number of segments.Then $$$n$$$ lines follow. The $$$i$$$-th line contains four integers $$$x_{i, 1}$$$, $$$y_{i, 1}$$$, $$$x_{i, 2}$$$ and $$$y_{i, 2}$$$ denoting the endpoints of the $$$i$$$-th segment. All coordinates of the endpoints are in the range $$$[-5000, 5000]$$$.It is guaranteed that each segment is non-degenerate and is either horizontal or vertical. Furthermore, if two segments share a common point, one of these segments is horizontal, and another one is vertical.

Output: Print one integer — the number of ways to choose four segments so they form a rectangle.

Note: The following pictures represent sample cases:    

Sample Inputs:
7
-1 4 -1 -2
6 -1 -2 -1
-2 3 6 3
2 -2 2 4
4 -1 4 3
5 3 5 1
5 2 1 2

5
1 5 1 0
0 1 5 1
5 4 0 4
4 2 4 0
4 3 4 5

Sample Outputs:
7

0

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum_segment(s, t):
    ans = get_sum(t) - get_sum(s - 1)
    return ans

def add(i, x):
    while i <= m:
        tree[i] += x
        i += i & -i
n = int(input())
(x, y) = ([], [])
c = 5001
for _ in range(n):
    (x1, y1, x2, y2) = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            (y1, y2) = (y2, y1)
        x.append((x1 + c, y1 + c, y2 + c))
    else:
        if x1 > x2:
            (x1, x2) = (x2, x1)
        y.append((y1 + c, x1 + c, x2 + c))
if len(x) < len(y):
    (x, y) = (y, x)
m = 10005
x.sort()
y = [(yi[2], yi[0], yi[1]) for yi in y]
y.sort(reverse=True)
cnt = [0] * c
for i in range(len(x) - 1):
    (x1, y1, y2) = x[i]
    tree = make_tree(m)
    k = 0
    for j in range(len(x) - 1, i, -1):
        (x2, y3, y4) = x[j]
        while k < len(y) and y[k][0] >= x2:
            (r, h, l) = y[k]
            if y1 <= h <= y2 and l <= x1:
                add(h, 1)
            k += 1
        cnt[get_sum_segment(y3, y4)] += 1
ans = 0
for i in range(1, c):
    ans += cnt[i] * i * (i - 1) // 2
print(ans)

Solution (Python):
import sys
from array import array
import typing as Tp

def input():
    return sys.stdin.buffer.readline().decode('utf-8')
T = Tp.TypeVar('T')

class FenwickSum(Tp.Generic[T]):
    __slots__ = ['nodes', 'size', 'unit']

    def __init__(self, size: int, default: T, unit: T):
        self.nodes = [default] * (size + 1)
        self.size = size + 1
        self.unit = unit

    def add(self, index: int, value: T):
        while index < self.size:
            self.nodes[index] += value
            index += index & -index

    def sum(self, right: int) -> T:
        result = self.unit
        while right:
            result += self.nodes[right]
            right -= right & -right
        return result

def main():
    n = int(input())
    (vertical, horizontal) = ([], [])
    for (x1, y1, x2, y2) in (map(lambda x: int(x) + 5002, input().split()) for _ in range(n)):
        if x1 > x2:
            (x1, x2) = (x2, x1)
        if y1 > y2:
            (y1, y2) = (y2, y1)
        if x1 == x2:
            vertical.append((x1, y1, x2, y2))
        else:
            horizontal.append((x1, y1, x2, y2))
    vertical.sort()
    horizontal.sort(key=lambda p: -p[2])
    ans = 0
    bit = FenwickSum[int](10010, 0, 0)
    for (i, (x1, y1, x2, y2)) in enumerate(vertical):
        stack = []
        for (x3, y3, x4, y4) in horizontal:
            if y1 <= y3 <= y2 and x3 <= x1 <= x4:
                stack.append((x4, y3))
                bit.add(y3, 1)
        for (x3, y3, x4, y4) in vertical[i + 1:]:
            while stack and stack[-1][0] < x3:
                bit.add(stack.pop()[1], -1)
            cnt = bit.sum(y4) - bit.sum(y3 - 1)
            ans += cnt * (cnt - 1) >> 1
        for (_, y) in stack:
            bit.add(y, -1)
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_tree(n):
    tree = [0] * (n + 1)
    return tree

def get_sum(i):
    s = 0
    while i > 0:
        s += tree[i]
        i -= i & -i
    return s

def get_sum_segment(s, t):
    ans = get_sum(t) - get_sum(s - 1)
    return ans

def add(i, x):
    while i <= m:
        tree[i] += x
        i += i & -i
n = int(input())
(x, y) = ([], [])
c = 5001
for _ in range(n):
    (x1, y1, x2, y2) = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            (y1, y2) = (y2, y1)
        x.append((x1 + c, y1 + c, y2 + c))
    else:
        if x1 > x2:
            (x1, x2) = (x2, x1)
        y.append((y1 + c, x1 + c, x2 + c))
if len(x) < len(y):
    (x, y) = (y, x)
m = 10005
x.sort()
y = [(yi[2], yi[0], yi[1]) for yi in y]
y.sort(reverse=True)
cnt = [0] * c
for i in range(len(x) - 1):
    (x1, y1, y2) = x[i]
    tree = make_tree(m)
    k = 0
    for j in range(len(x) - 1, i, -1):
        (x2, y3, y4) = x[j]
        while k < len(y) and y[k][0] >= x2:
            (r, h, l) = y[k]
            if y1 <= h <= y2 and l <= x1:
                add(h, 1)
            k += 1
        cnt[get_sum_segment(y3, y4)] += 1
ans = 0
for i in range(1, c):
    ans += cnt[i] * i * (i - 1) // 2
print(ans)