結果

問題 No.1074 増殖
コンテスト
ユーザー gew1fw
提出日時 2025-06-12 14:31:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,552 bytes
コンパイル時間 182 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 90,240 KB
最終ジャッジ日時 2025-06-12 14:31:52
合計ジャッジ時間 4,136 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 3 TLE * 1 -- * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def readints():
    return list(map(int, sys.stdin.readline().split()))

def main():
    N = int(sys.stdin.readline())
    rectangles = []
    for _ in range(N):
        Xa, Ya, Xb, Yb = readints()
        rectangles.append(((Xa, Ya), (Xb, Yb)))

    union = []
    for rect in rectangles:
        Xa, Ya = rect[0]
        Xb, Yb = rect[1]
        current_area = (Xb - Xa) * (Yb - Ya)

        covered_area = 0

        to_remove = []
        new_rects = []
        new_rects.append((Xa, Ya, Xb, Yb))
        for r in union:
            a, b, c, d = r
            # Check if new_rects intersect with r
            for i in range(len(new_rects)):
                x1, y1, x2, y2 = new_rects[i]
                if not (x2 < a or x1 > c or y2 < b or y1 > d):
                    # Compute intersection
                    int_x1 = max(x1, a)
                    int_y1 = max(y1, b)
                    int_x2 = min(x2, c)
                    int_y2 = min(y2, d)
                    if int_x1 < int_x2 and int_y1 < int_y2:
                        area = (int_x2 - int_x1) * (int_y2 - int_y1)
                        covered_area += area
                        # Split the new_rect into non-overlapping parts
                        new_rects.pop(i)
                        # Check all possible subdivisions
                        if x1 < int_x1:
                            new_rects.append((x1, y1, int_x1, y2))
                        if y1 < int_y1:
                            new_rects.append((int_x1, y1, x2, int_y1))
                        if x2 > int_x2:
                            new_rects.append((int_x2, int_y1, x2, y2))
                        if y2 > int_y2:
                            new_rects.append((int_x1, int_y2, int_x2, y2))
                        # Check if any new_rect is valid
                        new_rects = [r for r in new_rects if r[0] < r[2] and r[1] < r[3]]
                        # Adjust new_rects
                        while i < len(new_rects):
                            x, y, xx, yy = new_rects[i]
                            if x >= xx or y >= yy:
                                new_rects.pop(i)
                            else:
                                i += 1
                        break
        # Add all new_rects to union
        for x, y, xx, yy in new_rects:
            if x < xx and y < yy:
                union.append((x, y, xx, yy))
        # The increase is current_area minus covered_area
        print(current_area - covered_area)

if __name__ == '__main__':
    main()
0