문제

2563번: 색종이

풀이

• 벤다이어그램이랑 같은 로직으로 풀었음

• A + B + C - (AnB + AnC + BnC) + AnBnC

• A

  • AnB
    • AnBnC
  • AnC

• B

  • BnC

• C

• 근데 이거 n! 임 아 ㅋㅋ

구현

import sys

N = int(input())
paper = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def intersect(p1, p2):
	x1 = max(p1[0], p2[0])
	y1 = max(p1[1], p2[1])
	x2 = min(p1[0] + p1[2], p2[0] + p2[2])
	y2 = min(p1[1] + p1[3], p2[1] + p2[3])
	return [x1, y1, max(x2 - x1, 0), max(y2 - y1, 0)]

def area(p):
	return p[2] * p[3]

def rec(box, i, flag):
	ret = 0
	for j in range(i, N):
		_box = intersect(box, [paper[j][0], paper[j][1], 10, 10])
		#print(i + 1 , j + 1, _box, area(_box), flag)
		if flag:
			ret += area(_box)
		else :
			ret -= area(_box)
		ret += rec(_box, j + 1, not flag)
	return ret

print(rec([0, 0, 100, 100], 0, True))