Problem:


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

Union of Rectangles

  Given a set of $N$ axis-aligned rectangles in the plane, find the area of regions which are covered by at least one rectangle.

Input

  The input is given in the following format.

$N$

$x1_1$ $y1_1$ $x2_1$ $y2_1$

$x1_2$ $y1_2$ $x2_2$ $y2_2$

:

$x1_N$ $y1_N$ $x2_N$ $y2_N$

($x1_i, y1_i$) and ($x2_i, y2_i$) are the coordinates of the top-left corner and the bottom-right corner of the $i$-th rectangle respectively.

Constraints

$ 1 \leq N \leq 2000 $

$ −10^9 \leq x1_i < x2_i\leq 10^9 $

$ −10^9 \leq y1_i < y2_i\leq 10^9 $

Output

  Print the area of the regions.

Sample Input 1

2
0 0 3 4
1 2 4 3

Sample Output 1

13

Sample Input 2

3
1 1 2 5
2 1 5 2
1 2 2 5

Sample Output 2

7

Sample Input 3

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

Sample Output 3

8



Sample input:
2
0 0 3 4
1 2 4 3


Sample output:
13

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import io, sys
import bisect


def main():
    N = int( sys.stdin.readline() )
    x1y1x2y2_list = [ list(map(int, sys.stdin.readline().split())) for _ in range(N) ]
    
    X1 = [a for a,b,c,d in x1y1x2y2_list]
    X2 = [c for a,b,c,d in x1y1x2y2_list]
    Y1 = [b for a,b,c,d in x1y1x2y2_list]
    Y2 = [d for a,b,c,d in x1y1x2y2_list]

    all_X = compress(X1,X2)
    all_Y = compress(Y1,Y2)

    matrix =[ [0]*len(all_X) for _ in range(len(all_Y)) ]

    for i in range(N):
        matrix[ Y1[i] ][ X1[i] ] += 1
        matrix[ Y2[i] ][ X2[i] ] += 1
        matrix[ Y2[i] ][ X1[i] ] -= 1
        matrix[ Y1[i] ][ X2[i] ] -= 1

    for row in range(len(matrix)):
        for col in range(1, len(matrix[0])):
            matrix[row][col] += matrix[row][col-1]
    
    for row in range(1, len(matrix)):
        for col in range(len(matrix[0])):
            matrix[row][col] += matrix[row-1][col]

    ans = 0

    for row in range(len(matrix)):
        for col in range(len(matrix[0])):
            if matrix[row][col] > 0:
                area = (all_X[col+1] - all_X[col]) * (all_Y[row+1] - all_Y[row])
                ans += area

    print(ans)


def compress(A1 :list, A2 :list):
    all_A = []
    #delta = [-1, 0, 1]
    delta = [0]

    for a in (A1 + A2):
        for d in delta:
            all_A.append(a + d)
    
    all_A = sorted(set(all_A))

    for i in range(len(A1)):
        A1[i] = bisect.bisect_left(all_A, A1[i])
        A2[i] = bisect.bisect_left(all_A, A2[i])
    
    return all_A


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())

    xs = set()
    ys = set()
    rect = []
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        xs.add(x1)
        xs.add(x2)
        ys.add(y1)
        ys.add(y2)
        rect.append((x1, y1, x2, y2))
    X = sorted(xs)
    Y = sorted(ys)
    dx = {x: i for i, x in enumerate(X)}
    dy = {y: i for i, y in enumerate(Y)}
    #print(dx, dy, dx[1])
    
    H = len(xs)
    W = len(ys)
    grid = [[0] * (W + 1) for _ in range(H + 1)]
    for x1, y1, x2, y2 in rect:
        grid[dx[x1]][dy[y1]] += 1
        grid[dx[x2]][dy[y1]] -= 1
        grid[dx[x1]][dy[y2]] -= 1
        grid[dx[x2]][dy[y2]] += 1
    #print(grid)
    for i in range(H):
        grid[i] = list(accumulate(grid[i]))
    #print(grid)
    for i in range(H):
        for j in range(W):
            grid[i + 1][j] += grid[i][j]
    #print(grid)
    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j]:
                ans += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)


def main():
    N = int(input())

    xs = set()
    ys = set()
    rect = []
    for _ in range(N):
        x1, y1, x2, y2 = map(int, input().split())
        xs.add(x1)
        xs.add(x2)
        ys.add(y1)
        ys.add(y2)
        rect.append((x1, y1, x2, y2))
    X = sorted(xs)
    Y = sorted(ys)
    dx = {x: i for i, x in enumerate(X)}
    dy = {y: i for i, y in enumerate(Y)}

    H = len(xs)
    W = len(ys)
    grid = [[0] * (W + 1) for _ in range(H + 1)]
    for x1, y1, x2, y2 in rect:
        grid[dx[x1]][dy[y1]] += 1
        grid[dx[x2]][dy[y1]] -= 1
        grid[dx[x1]][dy[y2]] -= 1
        grid[dx[x2]][dy[y2]] += 1

    for i in range(H):
        grid[i] = list(accumulate(grid[i]))
    for i in range(H):
        for j in range(W):
            grid[i + 1][j] += grid[i][j]

    ans = 0
    for i in range(H):
        for j in range(W):
            if grid[i][j]:
                ans += (X[i + 1] - X[i]) * (Y[j + 1] - Y[j])
    return ans


if __name__ == "__main__":
    print(main())

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque
from heapq import heappush, heappop
from itertools import permutations, accumulate
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

bl = bisect.bisect_left
br = bisect.bisect_right

def solve():
    n = I()
    p = LIR(n)
    fx = {x for (x, _, _, _) in p} | {x for (_, _, x, _) in p}
    fx = list(fx)
    fx.sort()
    fy = {y for (_, y, _, _) in p} | {y for (_, _, _, y) in p}
    fy = list(fy)
    fy.sort()
    h,w = len(fy),len(fx)
    a = [[0]*w for i in range(h)]
    for x1,y1,x2,y2 in p:
        l,u,r,d = bl(fx,x1),bl(fy,y1),bl(fx,x2),bl(fy,y2)
        a[u][l] += 1
        a[u][r] -= 1
        a[d][l] -= 1
        a[d][r] += 1
    s = [list(accumulate(i)) for i in a]
    for j in range(w):
        for i in range(h-1):
            s[i+1][j] += s[i][j]
    ans = 0
    for i in range(h-1):
        y = fy[i+1]-fy[i]
        for j in range(w-1):
            if s[i][j]:
                x = fx[j+1]-fx[j]
                ans += x*y
    print(ans)
    return

#Solve
if __name__ == "__main__":
    solve()

Submission status: Accepted

Solution code:
#import bisect
#from collections import product
n = int(input())

co_x = set()
co_y = set()
Rec = []
for _ in range(n):
    x1,y1,x2,y2 = map(int, input().split( ))
    co_x = co_x | {x1,x2}
    co_y = co_y | {y1,y2}
    Rec.append([x1,y1,x2,y2])

Rec.sort()

co_x = list(co_x)
co_y = list(co_y)

co_x.sort()
co_y.sort()

r = len(co_x)
l = len(co_y)

#Rec_press = []
"""
for p in Rec:
    ix0 = bisect.bisect_left(co_x,p[0])
    iy0 = bisect.bisect_left(co_x,p[1])
    ix1 = bisect.bisect_left(co_x,p[2])
    iy1 = bisect.bisect_left(co_x,p[3])
    Rec_press.append([ix0,iy0,ix1,iy1])
    
#以上圧縮

"""
#3161838 By JAKENU0X5E参照
mx = {x:i for i,x in enumerate(co_x)}
my = {y:i for i,y in enumerate(co_y)}
h = len(mx)
w = len(my)
#print(mx,my)

s = [[0]*(w+1) for i in range(h+1)]
for p in Rec:
    p1 = mx[p[0]]
    q1 = my[p[1]]
    p2 = mx[p[2]]
    q2 = my[p[3]]
    
    s[p1][q1] += 1
    s[p1][q2] -= 1
    s[p2][q1] -= 1
    s[p2][q2] += 1

"""
この時点でのs[p][q]は被覆開始のフラグ
次のforで直前のs[i][j]に応じてs[i][j+1],s[i+1][j+1]を+1することで
sが被覆されているか否かのフラグになる
"""
    

for i in range(h):
    for j in range(w):
        s[i][j+1] += s[i][j]
for j in range(w):
    for i in range(h):
        s[i+1][j] += s[i][j]

ans = 0

for i in range(h):
    for j in range(w):
        if s[i][j]:
            #print(co_x[i],co_y[j],co_x[i+1],co_y[j+1],(co_x[i+1]-co_x[i])*(co_y[j+1]-co_y[j]))
            ans += (co_x[i+1]-co_x[i])*(co_y[j+1]-co_y[j])

print(ans)

Submission status: Accepted

Solution code:
from typing import List, Iterator, Tuple


class Rectangle(object):
    def __init__(self, xy1: Tuple[int, int], xy2: Tuple[int, int]) -> None:
        self.topleft = xy1
        self.bottomright = xy2

    def area(self) -> int:
        x1, y1 = self.topleft
        x2, y2 = self.bottomright
        return (x2 - x1) * (y2 - y1)


class MergetdRectangles(object):
    def __init__(self) -> None:
        self.rects: List[Rectangle] = []

    def _intersect(self, base_rect: Rectangle, new_rect: Rectangle) -> bool:
        x1, y1 = base_rect.topleft
        x2, y2 = base_rect.bottomright
        xn1, yn1 = new_rect.topleft
        xn2, yn2 = new_rect.bottomright

        if (xn2 <= x1 or x2 <= xn1):
            return False

        if (yn2 <= y1 or y2 <= yn1):
            return False

        return True

    def _sub(self, base_rect: Rectangle, new_rect: Rectangle) -> Iterator[Rectangle]:
        x1, y1 = base_rect.topleft
        x2, y2 = base_rect.bottomright
        xn1, yn1 = new_rect.topleft
        xn2, yn2 = new_rect.bottomright
        if (x1 < xn1):
            yield Rectangle((x1, y1), (xn1, y2))
        if (xn2 < x2):
            yield Rectangle((xn2, y1), (x2, y2))
        if (y1 < yn1):
            yield Rectangle((max(x1, xn1), y1), (min(x2, xn2), yn1))
        if (yn2 < y2):
            yield Rectangle((max(x1, xn1), yn2), (min(x2, xn2), y2))

    def add(self, new_rect: Rectangle) -> None:
        rects: List[Rectangle] = []
        for r in self.rects:
            if self._intersect(r, new_rect):
                rects.extend(self._sub(r, new_rect))
            else:
                rects.append(r)
        rects.append(new_rect)
        self.rects = rects

    def total_area(self) -> int:
        return sum([r.area() for r in self.rects])


if __name__ == "__main__":
    N = int(input())
    rects = MergetdRectangles()
    for _ in range(N):
        x1, y1, x2, y2 = map(lambda x: int(x), input().split())
        rects.add(Rectangle((x1, y1), (x2, y2)))
    print(rects.total_area())

Submission status: Accepted

Solution code:
N = int(input())

xs = set();ys = set()
P = []
for i in range(N):
    x1,y1,x2,y2 = map(int, input().split())
    xs.add(x1);xs.add(x2)
    ys.add(y1);ys.add(y2)
    P.append((x1,x2,y1,y2))
    
X = sorted(xs);Y = sorted(ys)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}

H = len(Y);W = len(X)
S = [[0]*(W+1) for i in range(H+1)]
for x1, x2, y1, y2 in P:
    p1 = MY[y1]; q1 = MX[x1]
    p2 = MY[y2]; q2 = MX[x2]
    
    S[p1][q1] += 1
    S[p1][q2] -= 1
    S[p2][q1] -= 1
    S[p2][q2] += 1

#右側に囲まれている長方形の辺があれば正になる？
for i in range(H):
    for j in range(W):
        S[i][j+1] += S[i][j]
#上側に囲まれている長方形の辺があれば正になる？
for j in range(W):
    for i in range(H):
        S[i+1][j]+= S[i][j]
        
ans = 0

for i in range(H):
    for j in range(W):
        if S[i][j]:
            ans += (Y[i+1]-Y[i])*(X[j+1]-X[j])
print(ans)

Submission status: Accepted

Solution code:
N = int(input())

XS = set(); YS = set()

P = []
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    XS.add(x1); XS.add(x2)
    YS.add(y1); YS.add(y2)
    P.append((x1, y1, x2, y2))

X = sorted(XS); Y = sorted(YS)
MX = {x: i for i, x in enumerate(X)}
MY = {y: i for i, y in enumerate(Y)}

H = len(Y); W = len(X)
S = [[0]*(W+1) for i in range(H+1)]
for x1, y1, x2, y2 in P:
    p1 = MY[y1]; q1 = MX[x1]
    p2 = MY[y2]; q2 = MX[x2]

    S[p1][q1] += 1
    S[p1][q2] -= 1
    S[p2][q1] -= 1
    S[p2][q2] += 1

for i in range(H):
    for j in range(W):
        S[i][j+1] += S[i][j]
for j in range(W):
    for i in range(H):
        S[i+1][j] += S[i][j]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j]:
            ans += (Y[i+1] - Y[i]) * (X[j+1] - X[j])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
# DSL_4_A: Union of Rectangles
# O(N^2)


class Rect:
    def __init__(self, p1, p2):
        self.top_left = p1
        self.bottom_right = p2

    def intersect(self, other):
        xs1, ys1 = self.top_left
        xs2, ys2 = self.bottom_right
        xo1, yo1 = other.top_left
        xo2, yo2 = other.bottom_right

        if xs1 >= xo2:
            return False
        elif xs2 <= xo1:
            return False

        if ys1 >= yo2:
            return False
        elif ys2 <= yo1:
            return False

        return True

    def sub(self, other):
        # assert self.intersect(other), "{} {}".format(self, other)
        xs1, ys1 = self.top_left
        xs2, ys2 = self.bottom_right
        xo1, yo1 = other.top_left
        xo2, yo2 = other.bottom_right
        if xs1 < xo1:
            yield Rect((xs1, ys1), (xo1, ys2))
        if xs2 > xo2:
            yield Rect((xo2, ys1), (xs2, ys2))
        if ys1 < yo1:
            yield Rect((max(xs1, xo1), ys1), (min(xs2, xo2), yo1))
        if ys2 > yo2:
            yield Rect((max(xs1, xo1), yo2), (min(xs2, xo2), ys2))

    def area(self):
        x1, y1 = self.top_left
        x2, y2 = self.bottom_right
        return (x2 - x1) * (y2 - y1)

    def __str__(self):
        return '<Rect({}, {})>'.format(self.top_left, self.bottom_right)


class Rects:
    def __init__(self):
        self.rects = []

    def add(self, rect):
        rects = []
        for r in self.rects:
            if rect.intersect(r):
                rects.extend(r.sub(rect))
            else:
                rects.append(r)
        rects.append(rect)
        self.rects = rects
        # assert self.not_intersect(), self

    def area(self):
        return sum([r.area() for r in self.rects])

    def __str__(self):
        s = '<Rects('
        s += '\n       '.join(str(r) for r in self.rects)
        s += ')>'
        return s

    def not_intersect(self):
        for i in range(len(self.rects)-1):
            for j in range(i+1, len(self.rects)):
                if self.rects[i].intersect(self.rects[j]):
                    return False
        return True


def run():
    n = int(input())
    rects = Rects()
    for _ in range(n):
        x1, y1, x2, y2 = [int(i) for i in input().split()]
        rect = Rect((x1, y1), (x2, y2))
        rects.add(rect)

    print(rects.area())


if __name__ == '__main__':
    run()