레이팅 미적용지도 출판은 쉬운 일이 아니다. 먼저 지구의 구형 표면을 2차원(t\(wo-di\)mensional) 평면에 표시하기 위한 적절한 변환이 필요하다. 그다음 또 다른 문제가 생긴다. 대부분의 고품질(hi\(gh-qu\)ality) 지도는 종이 한 장에 인쇄하기에는 너무 크다. 이를 해결하기 위해 지도 출판사들은 지도를 여러 직사각형 타일로 나누어 타일마다 한 페이지에 인쇄하곤 한다. 이 문제에서는 이 “타일링” 과정을 살펴본다. International Cartographic Publishing Company(ICPC)는 지도에 사용하는 타일 수를 최소화하여(mi\(ni- mi\)zing) 인쇄 비용을 줄여야 한다. 타일 크기(페이지 크기로 결정됨)와 지도 축척이 고정되어 있어도, 타일 격자를 조정하여 상황을 최적화할 수 있다. 그림 G.1의 왼쪽은 한 지역을 덮는 지도 타일 14개를 보여 준다. 오른쪽은 타일의 크기나 방향을 바꾸지 않고 같은 지역을 타일 10개만으로 덮는 방법을 보여 준다. 그림 G.1: 텍사스를 타일링하는 두 가지 방법. 당신의 임무는 ICPC가 주어진 지역을 덮는 데 필요한 최소 타일 수를 찾도록 돕는 것이다. 단순화를 위해 지역은 자기 자신과 교차하지 않는 닫힌 다각형으로 주어진다. 타일들은 \(x-ax\)is와 \(y-ax\)is에 정렬된 직사각형 격자의 일부여야 한다는 점에 유의하라. 즉, 타일들은 변 전체로만 서로 닿으며 회전할 수 없다. 또한 모든 입력 좌표는 정수이지만 타일은 정수가 아닌(n\(on-in\)teger) 좌표에 놓일 수 있음에 유의하라. 다각형은 가장자리 경계선에 닿을 수 있다(샘플 입력 2처럼). 하지만 부동소수점(floati\(ng- po\)int) 문제를 피하기 위해, 다각형이 지도 타일 밖으로 \(10^{−}^{6}\)의 거리까지 나가는 것을 허용해도 최적 답은 변하지 않는다고 가정해도 된다.
입력은 하나의 테스트 케이스로 이루어져 있다. 테스트 케이스의 첫 줄에는 세 정수 \(n\), \(xs\), \(ys\)가 주어진다. 다각형 꼭짓점의 수는 \(n\) (\(3 \le n \le 50\))이고, \(x_{s}\)와 \(y_{s}\) (\(1 \le x_{s}\), \(y_{s} \le 100\))는 각 타일의 크기이다. 다음 \(n\)개의 줄에는 지역을 나타내는 다각형의 꼭짓점을 지정하는 두 정수 \(x\)와 \(y\) (\(0 \le x \le 10x_{s}\), \(0 \le y \le 10y_{s}\))가 (시계 방향 또는 반시계 방향(count\(er-cl\)ockwise) 순서로) 주어진다.
다각형의 내부 전체를 덮는 데 필요한 최소 타일 수를 출력한다.
12 9 9
1 8
1 16
6 16
9 29
19 31
23 24
30 23
29 18
20 12
22 8
14 0
14 8
10
4 5 7
10 10
15 10
15 17
10 17
1