시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
20 초 128 MB 0 0 0 0.000%

문제

지도를 만드는 일은 쉬운 일이 아니다. 지구는 구형이기 때문에, 2차원 평면에 나타낼 때 왜곡이 발생한다. 또, 고화질 지도는 매우 크기 때문에, 종이 한장에 인쇄할 수 없다. 따라서, 지도를 여러 부분으로 쪼갠 나눈 다음 종이 여러 개에 인쇄를 해 합친다.

상근이는 지도를 제작하고 있다. 상근이는 항상 이익만을 추구하기 때문에, 종이를 최대한 적게 사용해 지도를 인쇄하려고 한다. 종이의 크기는 모두 같다.

왼쪽 그림은 한 지도를 종이 14개에 인쇄한 것이고, 오른쪽 그림은 같은 지도를 종이 10개에 인쇄한 것이다. 두 지도 모두 같은 종이를 사용하며, 종이의 크기와 방향은 모두 같다.

지도가 주어졌을 때, 지도를 인쇄하는데 필요한 종이 개수의 최소값을 구하는 프로그램을 작성하시오. 지도는 모두 닫힌 다각형이고, 교차하지 않는다.

종이는 모두 직사각형이고, x축과 y축에 평행해야 한다. 서로 접하는 종이의 꼭지점은 일치해야 하고, 종이를 회전할 수는 없다. 입력으로 주어지는 모든 좌표는 정수이지만, 종이는 정수가 아닌 좌표에 놓을 수 있다.

지도는 종이의 외각선에 접해도 된다. 소수점 계산으로 생기는 오차를 피하기 위해, 지도가 종이의 바깥으로 10-6 까지 넘어가도 정답은 같다.

입력

첫째 줄에 지도의 꼭지점의 수 n (3 ≤ n ≤ 50), 종이의 크기 xs, ys (1 ≤ xs, ys ≤ 100)이 주어진다.

다음 n개 줄에는 지도의 꼭지점을 나타내는 두 정수 x와 y가 주어진다. (0 ≤ x ≤ 10xs, 0 ≤ y ≤ 10ys) 꼭지점은 시계방향 또는 반시계방향으로 주어진다.

출력

첫째 줄에 지도를 인쇄하기 위해 필요한 종이 개수의 최소값을 출력한다.

예제 입력 1

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

예제 출력 1

10

힌트

W3sicHJvYmxlbV9pZCI6Ijg4ODMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM4ODVcdWM3NzQgXHVjOWMwXHViM2M0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIzYzRcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1Yzc3Y1x1Yzc0MCBcdWMyNmNcdWM2YjQgXHVjNzdjXHVjNzc0IFx1YzU0NFx1YjJjOFx1YjJlNC4gXHVjOWMwXHVhZDZjXHViMjk0IFx1YWQ2Y1x1ZDYxNVx1Yzc3NFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIDJcdWNjMjhcdWM2ZDAgXHVkM2M5XHViYTc0XHVjNWQwIFx1YjA5OFx1ZDBjMFx1YjBiYyBcdWI1NGMgXHVjNjVjXHVhY2UxXHVjNzc0IFx1YmMxY1x1YzBkZFx1ZDU1Y1x1YjJlNC4gXHViNjEwLCBcdWFjZTBcdWQ2NTRcdWM5YzggXHVjOWMwXHViM2M0XHViMjk0IFx1YjllNFx1YzZiMCBcdWQwNmNcdWFlMzAgXHViNTRjXHViYjM4XHVjNWQwLCBcdWM4ODVcdWM3NzQgXHVkNTVjXHVjN2E1XHVjNWQwIFx1Yzc3OFx1YzFjNFx1ZDU2MCBcdWMyMTggXHVjNWM2XHViMmU0LiBcdWI1MzBcdWI3N2NcdWMxMWMsIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM1ZWNcdWI3ZWMgXHViZDgwXHViZDg0XHVjNzNjXHViODVjIFx1Y2FiY1x1YWMyMCBcdWIwOThcdWIyMDggXHViMmU0XHVjNzRjIFx1Yzg4NVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNWQwIFx1Yzc3OFx1YzFjNFx1Yjk3YyBcdWQ1NzQgXHVkNTY5XHVjZTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjOWMwXHViM2M0XHViOTdjIFx1YzgxY1x1Yzc5MVx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjNzc0XHVjNzc1XHViOWNjXHVjNzQ0IFx1Y2Q5NFx1YWQ2Y1x1ZDU1OFx1YWUzMCBcdWI1NGNcdWJiMzhcdWM1ZDAsIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWNkNWNcdWIzMDBcdWQ1NWMgXHVjODAxXHVhYzhjIFx1YzBhY1x1YzZhOVx1ZDU3NCBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjNzc4XHVjMWM0XHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC4gXHVjODg1XHVjNzc0XHVjNzU4IFx1ZDA2Y1x1YWUzMFx1YjI5NCBcdWJhYThcdWI0NTAgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM2N2NcdWNhYmQgXHVhZGY4XHViOWJjXHVjNzQwIFx1ZDU1YyBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjODg1XHVjNzc0IDE0XHVhYzFjXHVjNWQwIFx1Yzc3OFx1YzFjNFx1ZDU1YyBcdWFjODNcdWM3NzRcdWFjZTAsIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWFkZjhcdWI5YmNcdWM3NDAgXHVhYzE5XHVjNzQwIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM4ODVcdWM3NzQgMTBcdWFjMWNcdWM1ZDAgXHVjNzc4XHVjMWM0XHVkNTVjIFx1YWM4M1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1YzljMFx1YjNjNCBcdWJhYThcdWI0NTAgXHVhYzE5XHVjNzQwIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NThcdWJhNzAsIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWQwNmNcdWFlMzBcdWM2NDAgXHViYzI5XHVkNWE1XHVjNzQwIFx1YmFhOFx1YjQ1MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvdGlsZSgyKS5wbmdcIiBzdHlsZT1cImhlaWdodDoyMjBweDsgd2lkdGg6Mzk1cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjOWMwXHViM2M0XHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YzljMFx1YjNjNFx1Yjk3YyBcdWM3NzhcdWMxYzRcdWQ1NThcdWIyOTRcdWIzNzAgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1Yzg4NVx1Yzc3NCBcdWFjMWNcdWMyMThcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM5YzBcdWIzYzRcdWIyOTQgXHViYWE4XHViNDUwIFx1YjJlYlx1ZDc4YyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NzRcdWFjZTAsIFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWIyOTRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzg4NVx1Yzc3NFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjOWMxXHVjMGFjXHVhYzAxXHVkNjE1XHVjNzc0XHVhY2UwLCB4XHVjZDk1XHVhY2ZjIHlcdWNkOTVcdWM1ZDAgXHVkM2M5XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjMTFjXHViODVjIFx1YzgxMVx1ZDU1OFx1YjI5NCBcdWM4ODVcdWM3NzRcdWM3NTggXHVhZjJkXHVjOWMwXHVjODEwXHVjNzQwIFx1Yzc3Y1x1Y2U1OFx1ZDU3NFx1YzU3YyBcdWQ1NThcdWFjZTAsIFx1Yzg4NVx1Yzc3NFx1Yjk3YyBcdWQ2OGNcdWM4MDRcdWQ1NjAgXHVjMjE4XHViMjk0IFx1YzVjNlx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWJhYThcdWI0ZTAgXHVjODhjXHVkNDVjXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YzljMFx1YjljYywgXHVjODg1XHVjNzc0XHViMjk0IFx1YzgxNVx1YzIxOFx1YWMwMCBcdWM1NDRcdWIyY2MgXHVjODhjXHVkNDVjXHVjNWQwIFx1YjE5M1x1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM5YzBcdWIzYzRcdWIyOTQgXHVjODg1XHVjNzc0XHVjNzU4IFx1YzY3OFx1YWMwMVx1YzEyMFx1YzVkMCBcdWM4MTFcdWQ1NzRcdWIzYzQgXHViNDFjXHViMmU0LiBcdWMxOGNcdWMyMThcdWM4MTAgXHVhY2M0XHVjMGIwXHVjNzNjXHViODVjIFx1YzBkZFx1YWUzMFx1YjI5NCBcdWM2MjRcdWNjMjhcdWI5N2MgXHVkNTNjXHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCwgXHVjOWMwXHViM2M0XHVhYzAwIFx1Yzg4NVx1Yzc3NFx1Yzc1OCBcdWJjMTRcdWFlNjVcdWM3M2NcdWI4NWMgMTA8c3VwPi02PFwvc3VwPiBcdWFlNGNcdWM5YzAgXHViMTE4XHVjNWI0XHVhYzAwXHViM2M0IFx1YzgxNVx1YjJmNVx1Yzc0MCBcdWFjMTlcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YzljMFx1YjNjNFx1Yzc1OCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVjMjE4IG4gKDMgJmxlOyBuICZsZTsgNTApLCBcdWM4ODVcdWM3NzRcdWM3NTggXHVkMDZjXHVhZTMwIHg8c3ViPnM8XC9zdWI+LCB5PHN1Yj5zPFwvc3ViPiAoMSAmbGU7IHg8c3ViPnM8XC9zdWI+LCB5PHN1Yj5zPFwvc3ViPiAmbGU7IDEwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjOWMwXHViM2M0XHVjNzU4IFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHViNDUwIFx1YzgxNVx1YzIxOCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMCAmbGU7IHggJmxlOyAxMHg8c3ViPnM8XC9zdWI+LCAwICZsZTsgeSAmbGU7IDEweTxzdWI+czxcL3N1Yj4pIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc0MCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTUgXHViNjEwXHViMjk0IFx1YmMxOFx1YzJkY1x1YWNjNFx1YmMyOVx1ZDVhNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWM5YzBcdWIzYzRcdWI5N2MgXHVjNzc4XHVjMWM0XHVkNTU4XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHVjODg1XHVjNzc0IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6Ijg4ODMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJNYXAgVGlsZXMiLCJkZXNjcmlwdGlvbiI6IjxwPlB1Ymxpc2hpbmcgbWFwcyBpcyBub3QgYW4gZWFzeSB0YXNrLiBGaXJzdCB5b3UgbmVlZCBzb21lIGFwcHJvcHJpYXRlIHRyYW5zZm9ybWF0aW9uIHRvIGRpc3BsYXkgdGhlIGVhcnRoJnJzcXVvO3Mgc3BoZXJpY2FsIHNoYXBlIGluIGEgdHdvLWRpbWVuc2lvbmFsIHBsYW5lLiBUaGVuIGFub3RoZXIgaXNzdWUgYXJpc2VzICZuZGFzaDsgbW9zdCBoaWdoLXF1YWxpdHkgbWFwcyBhcmUgdG9vIGxhcmdlIHRvIGJlIHByaW50ZWQgb24gYSBzaW5nbGUgcGFnZSBvZiBwYXBlci4gVG8gY29wZSB3aXRoIHRoYXQsIG1hcCBwdWJsaXNoZXJzIG9mdGVuIHNwbGl0IG1hcHMgaW50byBzZXZlcmFsIHJlY3Rhbmd1bGFyIHRpbGVzLCBhbmQgcHJpbnQgZWFjaCB0aWxlIG9uIG9uZSBwYWdlLiBJbiB0aGlzIHByb2JsZW0sIHlvdSB3aWxsIGV4YW1pbmUgdGhpcyAmbGRxdW87dGlsaW5nJnJkcXVvOyBwcm9jZXNzLjxcL3A+XHJcblxyXG48cD5UaGUgSW50ZXJuYXRpb25hbCBDYXJ0b2dyYXBoaWMgUHVibGlzaGluZyBDb21wYW55IChJQ1BDKSBuZWVkcyB0byBjdXQgdGhlaXIgcHJpbnRpbmcgY29zdHMgYnkgbWluaW1pemluZyB0aGUgbnVtYmVyIG9mIHRpbGVzIHVzZWQgZm9yIHRoZWlyIG1hcHMuIEV2ZW4gd2l0aCBhIFx1ZmIwMXhlZCB0aWxlIHNpemUgKGRldGVybWluZWQgYnkgdGhlIHBhZ2Ugc2l6ZSkgYW5kIG1hcCBzY2FsZSwgeW91IGNhbiBzdGlsbCBvcHRpbWl6ZSB0aGUgc2l0dWF0aW9uIGJ5IGFkanVzdGluZyB0aGUgdGlsZSBncmlkLjxcL3A+XHJcblxyXG48cD5UaGUgbGVmdCBzaWRlIG9mIEZpZ3VyZSBHLjEgc2hvd3MgMTQgbWFwIHRpbGVzIGNvdmVyaW5nIGEgcmVnaW9uLiBUaGUgcmlnaHQgc2lkZSBzaG93cyBob3cgeW91IGNhbiBjb3ZlciB0aGUgc2FtZSByZWdpb24gd2l0aCBvbmx5IDEwIHRpbGVzLCB3aXRob3V0IGNoYW5naW5nIHRoZSB0aWxlIHNpemVzIG9yIG9yaWVudGF0aW9uLjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3RpbGUoMikucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MjIwcHg7IHdpZHRoOjM5NXB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZ3VyZSBHLjE6IFR3byBwb3NzaWJsZSB3YXlzIG9mIHRpbGluZyBUZXhhcy48XC9wPlxyXG5cclxuPHA+WW91ciB0YXNrIGlzIHRvIGhlbHAgdGhlIElDUEMgXHVmYjAxbmQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHRpbGVzIG5lZWRlZCB0byBjb3ZlciBhIGdpdmVuIHJlZ2lvbi4gRm9yIHNpbXBsaWNpdHksIHRoZSByZWdpb24gd2lsbCBiZSBnaXZlbiBhcyBhIGNsb3NlZCBwb2x5Z29uIHRoYXQgZG9lcyBub3QgaW50ZXJzZWN0IGl0c2VsZi48XC9wPlxyXG5cclxuPHA+Tm90ZSB0aGF0IHRoZSB0aWxlcyBtdXN0IGJlIHBhcnQgb2YgYSByZWN0YW5ndWxhciBncmlkIGFsaWduZWQgd2l0aCB0aGUgeC1heGlzIGFuZCB5LWF4aXMuIFRoYXQgaXMsIHRoZXkgdG91Y2ggZWFjaCBvdGhlciBvbmx5IHdpdGggdGhlaXIgd2hvbGUgc2lkZXMgYW5kIGNhbm5vdCBiZSByb3RhdGVkLiBBbHNvIG5vdGUgdGhhdCBhbHRob3VnaCBhbGwgaW5wdXQgY29vcmRpbmF0ZXMgYXJlIGludGVnZXJzLCB0aWxlcyBtYXkgYmUgbG9jYXRlZCBhdCBub24taW50ZWdlciBjb29yZGluYXRlcy48XC9wPlxyXG5cclxuPHA+VGhlIHBvbHlnb24gbWF5IHRvdWNoIHRoZSBlZGdlcyBvZiBtYXJnaW5hbCBsaW5lcyAoYXMgaW4gU2FtcGxlIElucHV0IDIpLiBIb3dldmVyLCB0byBhdm9pZCBmbG9hdGluZyBwb2ludCBpc3N1ZXMsIHlvdSBtYXkgYXNzdW1lIHRoZSBvcHRpbWFsIGFuc3dlciB3aWxsIG5vdCBjaGFuZ2UgZXZlbiBpZiB0aGUgcG9seWdvbiBpcyBhbGxvd2VkIHRvIGdvIG91dHNpZGUgdGhlIG1hcCB0aWxlcyBieSBhIGRpc3RhbmNlIG9mIDEwPHN1cD4tNjxcL3N1cD4uPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29uc2lzdHMgb2YgYSBzaW5nbGUgdGVzdCBjYXNlLiBUaGUgXHVmYjAxcnN0IGxpbmUgb2YgYSB0ZXN0IGNhc2UgY29udGFpbnMgdGhyZWUgaW50ZWdlcnM6IG4sIHg8c3ViPnM8XC9zdWI+LCBhbmQgeTxzdWI+czxcL3N1Yj4uIFRoZSBudW1iZXIgb2YgcG9seWdvbiB2ZXJ0aWNlcyBpcyBuICgzICZsZTsgbiAmbGU7IDUwKSwgYW5kIHg8c3ViPnM8XC9zdWI+IGFuZCB5PHN1Yj5zPFwvc3ViPiAoMSAmbGU7IHg8c3ViPnM8XC9zdWI+LCB5PHN1Yj5zPFwvc3ViPiAmbGU7IDEwMCkgYXJlIHRoZSBkaW1lbnNpb25zIG9mIGVhY2ggdGlsZS4gRWFjaCBvZiB0aGUgbmV4dCBuIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyB4IGFuZCB5ICgwICZsZTsgeCAmbGU7IDEweDxzdWI+czxcL3N1Yj4sIDAgJmxlOyB5ICZsZTsgMTB5PHN1Yj5zPFwvc3ViPiksIHNwZWNpZnlpbmcgdGhlIHZlcnRpY2VzIG9mIHRoZSBwb2x5Z29uIHJlcHJlc2VudGluZyB0aGUgcmVnaW9uIChpbiBlaXRoZXIgY2xvY2t3aXNlIG9yIGNvdW50ZXItY2xvY2t3aXNlIG9yZGVyKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5EaXNwbGF5IHRoZSBtaW5pbWFsIG51bWJlciBvZiB0aWxlcyBuZWNlc3NhcnkgdG8gY292ZXIgdGhlIHdob2xlIGludGVyaW9yIG9mIHRoZSBwb2x5Z29uLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > World Finals > 2013 World Finals G번