結果
問題 |
No.1074 増殖
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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()