백준 색종이 문제를 통해서 본 점의 논리와 선의 논리

문제 출처 : https://www.acmicpc.net/problem/2563

보통 이 문제는 도화지를 쪼개서 작은 영역으로 나누고 그 영역이 색종이이의 영역인지 아닌지를 판별하여 구하면 된다.
어떻게 보면 유한요소법이다.

이에 대한 코드는 간단히 다음과 같다.

N = int(input())
paper = [[0]*100 for _ in range(100)]

for _ in range(N) :
    x, y = map(int, input().split())
    for i in range(x, x+10) :
        for j in range(y, y+10) :
            paper[i][j] = 1

covered_area = sum(row.count(1) for row in paper)
print(covered_area)

그런데 원래 우리가 초등학교 때 배운 수학에서
도형은 원래 선을 통해 이루어진다.
다각형은 여러 선분으로
타원, 원의 경우에는 곡선으로 이루어질 것이다.
그러니까, 이 문제는 선의 경계를 찾으면 된다.
어떻게 찾을 것인가?

입력받은 x와 그로부터 생기는 x+10
y와 그로부터 생기는 y+10 에 대한 직선을 생각한다.
이것들은 도화지를 분할할테고 곰곰히 생각하면 겹치는 영역은 무조건 이 선들을 따라서 생길 수 밖에 없다.
이 영역이 색종이의 영역인지 아닌지를 판별하면 된다.
코드는 다음과 같다.

import sys
input = sys.stdin.readline

N = int(input().strip())
squares = []
for _ in range(N):
    a, b = map(int, input().split())
    squares.append((a, b))

x_boundaries = set()
y_boundaries = set()
for a, b in squares:
    x_boundaries.add(a)
    x_boundaries.add(a + 10)
    y_boundaries.add(b)
    y_boundaries.add(b + 10)

x_boundaries = sorted(x_boundaries)
y_boundaries = sorted(y_boundaries)

def is_covered(x, y):
    for a, b in squares:
        if a <= x < a + 10 and b <= y < b + 10:
            return True
    return False

total_area = 0
for i in range(len(x_boundaries) - 1):
    for j in range(len(y_boundaries) - 1):
        mid_x = (x_boundaries[i] + x_boundaries[i+1]) / 2.0
        mid_y = (y_boundaries[j] + y_boundaries[j+1]) / 2.0
        if is_covered(mid_x, mid_y):
            total_area += (x_boundaries[i+1] - x_boundaries[i]) * (y_boundaries[j+1] - y_boundaries[j])
print(total_area)

도형을 경계를 구성하는 점과 선의 집합으로 바라본다면, 풀이 과정에서 점과 선을 모두 활용하는 것이
자연스럽다. 그러니까 점으로 생각한 풀이와 선으로 생각한 풀이 두 가지가 나올 수 있는 것이다.