PS 이야기

2차원 좌표계에 모든 변이 x축과 평행하거나 y축에 평행한 직사각형 하나와 선분 하나가 주어졌을 때 교차점의 개수를 구하는 문제다. 이 문제를 편하게 해결하기 위해 두 선분이 주어졌을 때 생기는 교차점의 개수를 세는 함수 intersect(line a, line b)를 생각하자. 두 선분이 서로 다른 직선 성분일 경우, ccw 함수를 이용하여 두 선분이 교차하는지 확인할 수 있다. 만약 교차하면 생기는 교차점의 개수는 1개이며, 교차하지 않는다면 교차점의 개수는 0이다. ccw(point a, point b, point c): (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y) 점 a에서 점 b로 갔다가 점 c로 갔을 때 꺽이는 방향이 시계 방향인지 반시계 방향인지 판별하는 함수(..

$1 \times 1$ 크기의 격자 $MN$ 개가 $M \times N$ 크기의 직사각형을 이루고 있다. 각 격자에는 얼룩이 묻어있을 수 있다. $3 \times 3$ 크기의 덮개를 써서 모든 얼룩을 덮고자 할 때, 필요한 덮개의 최소 개수를 구하는 문제다. 이 문제에서 중요한 것은 $M$ 제한이 $N$ 제한에 비해 현저히 작다는 점이다.한 열에 덮개를 배치하는 경우의 수를 생각해보자. 우선 최악의 경우를 고려하기 위해 $M=10$이라 생각하자. 하나의 덮개를 덮개의 가장 윗 행 번호로 표현하자. 같은 행 번호에 여러 덮개가 있으면 항상 비효율적이며, 9번 행과 10번 행으로 표현되는 덮개는 없다. 따라서 $2^8 = 256$가지를 생각할 수 있다. 좀 더 경우의 수를 줄여보자. 10개의 행을 모두 덮는..