시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB231478756432.545%

문제

소들의 반란이 있은 뒤, 이 소들은 포로로 잡은 인간들을 감시해야 했다. 소들은 (Px, Py)의 위치에 감옥을 짓고, 감옥 둘레에 가능한 한 여러 겹으로 담을 쌓아 포로들이 도망가기 힘들도록 하려 한다. 감옥은 하나의 점으로 표현된다.

이러한 목적을 달성하기 위해, 소들은 감옥 주변에 N개의 담 기둥을 세웠다. 각각의 담은 감옥을 완전히 감싸야 하고, 담 안에 (부분적으로라도) 포함되는 담이 있다면 이러한 담도 완전히 감싸야 한다. 즉, 담벼락이 교차하거나 한 점에서 만나서는 안 된다. 감옥과 담 기둥 중 어느 세 점도 일직선상에 있지 않다.

이러한 담 기둥들이 주어졌을 때, 겹치지 않는 최대의 중첩된 담의 겹 수를 구하는 프로그램을 작성하시오.

담은 여러 개의 담벼락이 연결된, 닫힌 다각형을 의미하고, 각각의 담벼락의 두 끝 점은 담 기둥 이어야 한다. 이러한 담 사이에는 반드시 약간이라도 공간이 있어야 한다. 즉, 서로 다른 두 담이 하나의 담벼락이나 담 기둥을 공유해서는 안 된다.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), Px, Py (-100,000 ≤ Px, Py ≤ 100,000)이 주어진다. 다음 N개의 줄에는 차례로 담 기둥의 좌표가 주어진다. 각각의 좌표는 절댓값이 100,000을 넘지 않는 정수이다.

출력

첫째 줄에 최대 겹 수를 출력한다.

예제 입력 1

8 -1 0
2 2
2 -2
-2 2
-2 -2
0 10
8 0
-12 1
1 -5

예제 출력 1

2
W3sicHJvYmxlbV9pZCI6IjIyNTQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMTBcdWM2MjUgXHVhYzc0XHVjMTI0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMxOGNcdWI0ZTRcdWM3NTggXHViYzE4XHViNzgwXHVjNzc0IFx1Yzc4OFx1Yzc0MCBcdWI0YTQsIFx1Yzc3NCBcdWMxOGNcdWI0ZTRcdWM3NDAgXHVkM2VjXHViODVjXHViODVjIFx1YzdhMVx1Yzc0MCBcdWM3NzhcdWFjMDRcdWI0ZTRcdWM3NDQgXHVhYzEwXHVjMmRjXHVkNTc0XHVjNTdjIFx1ZDU4OFx1YjJlNC4gXHVjMThjXHViNGU0XHVjNzQwIChQPHN1Yj54PFwvc3ViPiwgUDxzdWI+eTxcL3N1Yj4pXHVjNzU4IFx1YzcwNFx1Y2U1OFx1YzVkMCBcdWFjMTBcdWM2MjVcdWM3NDQgXHVjOWQzXHVhY2UwLCBcdWFjMTBcdWM2MjUgXHViNDU4XHViODA4XHVjNWQwIFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWQ1NWMgXHVjNWVjXHViN2VjIFx1YWNiOVx1YzczY1x1Yjg1YyBcdWIyZjRcdWM3NDQgXHVjMzEzXHVjNTQ0IFx1ZDNlY1x1Yjg1Y1x1YjRlNFx1Yzc3NCBcdWIzYzRcdWI5ZGRcdWFjMDBcdWFlMzAgXHVkNzk4XHViNGU0XHViM2M0XHViODVkIFx1ZDU1OFx1YjgyNCBcdWQ1NWNcdWIyZTQuIFx1YWMxMFx1YzYyNVx1Yzc0MCBcdWQ1NThcdWIwOThcdWM3NTggXHVjODEwXHVjNzNjXHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViN2VjXHVkNTVjIFx1YmFhOVx1YzgwMVx1Yzc0NCBcdWIyZWNcdWMxMzFcdWQ1NThcdWFlMzAgXHVjNzA0XHVkNTc0LCBcdWMxOGNcdWI0ZTRcdWM3NDAgXHVhYzEwXHVjNjI1IFx1YzhmY1x1YmNjMFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YjJmNCBcdWFlMzBcdWI0NjVcdWM3NDQgXHVjMTM4XHVjNmUwXHViMmU0LiBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmY0XHVjNzQwIFx1YWMxMFx1YzYyNVx1Yzc0NCBcdWM2NDRcdWM4MDRcdWQ3ODggXHVhYzEwXHVjMmY4XHVjNTdjIFx1ZDU1OFx1YWNlMCwgXHViMmY0IFx1YzU0OFx1YzVkMCAoXHViZDgwXHViZDg0XHVjODAxXHVjNzNjXHViODVjXHViNzdjXHViM2M0KSBcdWQzZWNcdWQ1NjhcdWI0MThcdWIyOTQgXHViMmY0XHVjNzc0IFx1Yzc4OFx1YjJlNFx1YmE3NCBcdWM3NzRcdWI3ZWNcdWQ1NWMgXHViMmY0XHViM2M0IFx1YzY0NFx1YzgwNFx1ZDc4OCBcdWFjMTBcdWMyZjhcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWM5ODksIFx1YjJmNFx1YmNiY1x1Yjc3ZFx1Yzc3NCBcdWFkNTBcdWNjMjhcdWQ1NThcdWFjNzBcdWIwOTggXHVkNTVjIFx1YzgxMFx1YzVkMFx1YzExYyBcdWI5Y2NcdWIwOThcdWMxMWNcdWIyOTQgXHVjNTQ4IFx1YjQxY1x1YjJlNC4gXHVhYzEwXHVjNjI1XHVhY2ZjIFx1YjJmNCBcdWFlMzBcdWI0NjUgXHVjOTExIFx1YzViNFx1YjI5MCBcdWMxMzggXHVjODEwXHViM2M0IFx1Yzc3Y1x1YzljMVx1YzEyMFx1YzBjMVx1YzVkMCBcdWM3ODhcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI3ZWNcdWQ1NWMgXHViMmY0IFx1YWUzMFx1YjQ2NVx1YjRlNFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjYjlcdWNlNThcdWM5YzAgXHVjNTRhXHViMjk0IFx1Y2Q1Y1x1YjMwMFx1Yzc1OCBcdWM5MTFcdWNjYTlcdWI0MWMgXHViMmY0XHVjNzU4IFx1YWNiOSBcdWMyMThcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuXHJcbjxwPlx1YjJmNFx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1YjJmNFx1YmNiY1x1Yjc3ZFx1Yzc3NCBcdWM1ZjBcdWFjYjBcdWI0MWMsIFx1YjJlYlx1ZDc4YyBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTU4XHVhY2UwLCBcdWFjMDFcdWFjMDFcdWM3NTggXHViMmY0XHViY2JjXHViNzdkXHVjNzU4IFx1YjQ1MCBcdWIwNWQgXHVjODEwXHVjNzQwIFx1YjJmNCBcdWFlMzBcdWI0NjUgXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjNzc0XHViN2VjXHVkNTVjIFx1YjJmNCBcdWMwYWNcdWM3NzRcdWM1ZDBcdWIyOTQgXHViYzE4XHViNGRjXHVjMmRjIFx1YzU3ZFx1YWMwNFx1Yzc3NFx1Yjc3Y1x1YjNjNCBcdWFjZjVcdWFjMDRcdWM3NzQgXHVjNzg4XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVjOTg5LCBcdWMxMWNcdWI4NWMgXHViMmU0XHViOTc4IFx1YjQ1MCBcdWIyZjRcdWM3NzQgXHVkNTU4XHViMDk4XHVjNzU4IFx1YjJmNFx1YmNiY1x1Yjc3ZFx1Yzc3NFx1YjA5OCBcdWIyZjQgXHVhZTMwXHViNDY1XHVjNzQ0IFx1YWNmNVx1YzcyMFx1ZDU3NFx1YzExY1x1YjI5NCBcdWM1NDggXHViNDFjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMSwwMDApLCBQPHN1Yj54PFwvc3ViPiwgUDxzdWI+eTxcL3N1Yj4gKC0xMDAsMDAwICZsZTsgUDxzdWI+eDxcL3N1Yj4sIFA8c3ViPnk8XC9zdWI+ICZsZTsgMTAwLDAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjYzI4XHViODQwXHViODVjIFx1YjJmNCBcdWFlMzBcdWI0NjVcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHVhYzAxXHVhYzAxXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NzQgMTAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1Y2Q1Y1x1YjMwMCBcdWFjYjkgXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMjU0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2FwdGl2ZXMgb2YgV2FyIiwiZGVzY3JpcHRpb24iOiI8cD5BZnRlciB0aGUgQm92aW5lIFVwcmlzaW5nIG9mIDIwMDIsIHRoZSBjb3dzIG11c3Qga2VlcCB3YXRjaCBvdmVyIHRoZSBsYXJnZSBudW1iZXIgb2YgaHVtYW4gcHJpc29uZXJzIHRoZXkgY2FwdHVyZWQuPFwvcD5cclxuXHJcbjxwPlRoZXkgaGF2ZSBhIHByaXNvbiBhdCBjb29yZGluYXRlIChQeCwgUHkpICh3aGVyZSAtMTAwLDAwMCAmbHQ7PSBQeCAmbHQ7PSAxMDAsMDAwIGFuZCAtMTAwLDAwMCAmbHQ7PSBQeSAmbHQ7PSAxMDAsMDAwKSBhbmQgdGhleSB3YW50IHRvIGNvbnN0cnVjdCBhcyBtYW55IGxheWVycyBvZiBmZW5jZXMgYXMgcG9zc2libGUgYXJvdW5kIHRoZSBwcmlzb24gdG8gbWFrZSBlc2NhcGUgYXMgZGlmZmljdWx0IGFzIHBvc3NpYmxlLiBJdCBpcyB1bmZvcnR1bmF0ZSB0aGF0LCBmb3IgdGhpcyBwcm9ibGVtLCB0aGUgcHJpc29uIGlzIG1vZGVsZWQgYXMgYSBzaW5nbGUgcG9pbnQuPFwvcD5cclxuXHJcbjxwPkluIG9yZGVyIHRvIGFjY29tcGxpc2ggdGhpcywgdGhleSBoYXZlIHBsYWNlZCBOICgzICZsdDs9IE4gJmx0Oz0gMTAwMCkgZmVuY2UgcG9zdHMgaW4gdGhlIHZpY2luaXR5IG9mIHRoZSBwcmlzb24uICZuYnNwO0VhY2ggZmVuY2UgY29tcGxldGVseSBzdXJyb3VuZHMgdGhlIHByaXNvbiBhbmQgYWxsIGZlbmNlcyBpbnNpZGUgaXQgKGkuZS4sIG5vIGZlbmNlIGNyb3NzaW5nKS4gQW1vbmcgdGhlIHNldCBvZiBhbGwgZmVuY2UgcG9zdCBsb2NhdGlvbnMgYW5kIHRoZSBwcmlzb24gbG9jYXRpb24sIG5vIHRocmVlIHBvaW50cyBhcmUgY29sbGluZWFyLiAmbmJzcDtHaXZlbiB0aGUgbG9jYXRpb25zIG9mIHRoZXNlIGZlbmNlIHBvc3RzLCB5b3UgbXVzdCBjb21wdXRlIHRoZSBtYXhpbXVtIG51bWJlciBvZiBsYXllcnMgb2Ygbm9uLWludGVyc2VjdGluZyBuZXN0ZWQgZmVuY2VzIHRoZSBjb3dzIGNhbiBjb25zdHJ1Y3QgYXJvdW5kIHRoZSBwcmlzb24gYnkgcGxhY2luZyBzdHJhaWdodCBmZW5jZSByYWlscyBiZXR3ZWVuIHRoZSBmZW5jZSBwb3N0cyB0aGV5IGhhdmUgY29uc3RydWN0ZWQuICZuYnNwO0EgZ3VhcmQgbXVzdCBiZSBhYmxlIHRvIHBhdHJvbCBiZXR3ZWVuIGVhY2ggcGFpciBvZiBuZXN0ZWQgZmVuY2VzIChhbmQgYmV0d2VlbiB0aGUgaW5uZXIgZmVuY2UgYW5kIHRoZSBwcmlzb24pLCBzbyBsZWF2ZSBhdCBsZWFzdCBhIHNtYWxsIGFtb3VudCBvZiBzcGFjZSBpbiB0aGUgbmVzdGluZ3MgKGkuZS4sIGRvbiYjMzk7dCBzaGFyZSBhIHZlcnRleCBiZXR3ZWVuIHR3byBuZXN0ZWQgZmVuY2VzKS48XC9wPlxyXG4iLCJpbnB1dCI6Ijx1bD5cclxuXHQ8bGk+TGluZSAxOiBUaHJlZSBzcGFjZS1zZXBhcmF0ZWQgaW50ZWdlcnM6IE4sIFB4LCBhbmQgUHkuPFwvbGk+XHJcblx0PGxpPkxpbmVzIDIuLk4rMTogVHdvIHNwYWNlLXNlcGFyYXRlZCBpbnRlZ2VycywgWGkgYW5kIFlpICgtMTAwMDAwICZsdDs9IFhpLCBZaSAmbHQ7PSAxMDAwMDApIHNwZWNpZnlpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIGEgZmVuY2UgcG9zdC48XC9saT5cclxuPFwvdWw+XHJcbiIsIm91dHB1dCI6IjxwPkEgc2luZ2xlIGxpbmUgd2l0aCBhIHNpbmdsZSBpbnRlZ2VyIHRoYXQgaXMgdGhlIG1heGltdW0gbnVtYmVyIG9mIGxheWVycyBvZiBmZW5jZXMuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Olympiad > USA Computing Olympiad > 2002-2003 Season > USACO January 2003 Contest > Green 3번