시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 413 65 43 16.863%

문제

때때로 주어진 점들 사이에서 볼록 껍질(Convex Hull)을 찾아내는 기술은 요긴하게 쓰인다. ACM 월드파이널에서 볼록 껍질을 응용해야 하는 문제가 출제되다 보니, 이걸 할 줄 아는 것은 참가자의 소양이 되었다.

이 작업은 크게 두 단계의 과정으로 이루어진다. 첫 번째 단계는 볼록 껍질을 이루는 점들을 찾아내는 것이고, 두 번째 단계는 이 점들을 반시계 방향으로 순서를 매기는 것이다. 첫 번째 단계는 이미 완료되었다고 할 때, 두 번째 단계를 수행하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 점의 개수 n이 주어진다. (3 <= n <= 100,000)

두 번째 줄부터 n개의 줄에 걸쳐 각 점에 대한 정보 x, y, c가 주어진다. x, y는 정수이며 절댓값이 1,000,000,000을 넘지 않고, c는 Y 또는 N인 문자이다. Y는 이 점이 볼록 껍질에 속해있음을, N이면 아님을 의미한다.

중복되는 점은 없으며, 모든 점이 한 직선 위에 있는 경우도 없다.

출력

첫 번째 줄에 볼록 껍질을 이루는 점의 개수를 출력한다.

이어서 한 줄에 하나씩 그 점들의 좌표를 x y 형태로 출력하는데, 이 점들은 반시계 방향으로 순서를 이루어야 한다. 첫 번째 좌표는 x좌표가 가장 작은 점이어야 하며, 만약 그런 좌표가 여러 개라면 그 중에서 y좌표가 가장 작은 점을 선택한다.

예제 입력 1

5
1 1 Y
1 -1 Y
0 0 N
-1 -1 Y
-1 1 Y

예제 출력 1

4
-1 -1
1 -1
1 1
-1 1
W3sicHJvYmxlbV9pZCI6IjQxODEiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJDb252ZXggSHVsbCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvY29udmV4LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMTBweDsgd2lkdGg6MjgwcHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHViNTRjXHViNTRjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcdWM4MTBcdWI0ZTQgXHVjMGFjXHVjNzc0XHVjNWQwXHVjMTFjIFx1YmNmY1x1Yjg1ZCBcdWFlY2RcdWM5YzgoQ29udmV4IEh1bGwpXHVjNzQ0IFx1Y2MzZVx1YzU0NFx1YjBiNFx1YjI5NCBcdWFlMzBcdWMyMjBcdWM3NDAgXHVjNjk0XHVhZTM0XHVkNTU4XHVhYzhjIFx1YzRmMFx1Yzc3OFx1YjJlNC4gQUNNIFx1YzZkNFx1YjRkY1x1ZDMwY1x1Yzc3NFx1YjExMFx1YzVkMFx1YzExYyBcdWJjZmNcdWI4NWQgXHVhZWNkXHVjOWM4XHVjNzQ0IFx1Yzc1MVx1YzZhOVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHViYjM4XHVjODFjXHVhYzAwIFx1Y2Q5Y1x1YzgxY1x1YjQxOFx1YjJlNCBcdWJjZjRcdWIyYzgsIFx1Yzc3NFx1YWM3OCBcdWQ1NjAgXHVjOTA0IFx1YzU0NFx1YjI5NCBcdWFjODNcdWM3NDAgXHVjYzM4XHVhYzAwXHVjNzkwXHVjNzU4IFx1YzE4Y1x1YzU5MVx1Yzc3NCBcdWI0MThcdWM1YzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NCBcdWM3OTFcdWM1YzVcdWM3NDAgXHVkMDZjXHVhYzhjIFx1YjQ1MCBcdWIyZThcdWFjYzRcdWM3NTggXHVhY2ZjXHVjODE1XHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzljNFx1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCZuYnNwO1x1YjJlOFx1YWNjNFx1YjI5NCBcdWJjZmNcdWI4NWQgXHVhZWNkXHVjOWM4XHVjNzQ0IFx1Yzc3NFx1YjhlOFx1YjI5NCBcdWM4MTBcdWI0ZTRcdWM3NDQgXHVjYzNlXHVjNTQ0XHViMGI0XHViMjk0IFx1YWM4M1x1Yzc3NFx1YWNlMCwgXHViNDUwIFx1YmM4OFx1YzlmOCBcdWIyZThcdWFjYzRcdWIyOTQgXHVjNzc0IFx1YzgxMFx1YjRlNFx1Yzc0NCBcdWJjMThcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWI5ZTRcdWFlMzBcdWIyOTQgXHVhYzgzXHVjNzc0XHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YjJlOFx1YWNjNFx1YjI5NCBcdWM3NzRcdWJiZjggXHVjNjQ0XHViOGNjXHViNDE4XHVjNWM4XHViMmU0XHVhY2UwIFx1ZDU2MCBcdWI1NGMsIFx1YjQ1MCBcdWJjODhcdWM5ZjggXHViMmU4XHVhY2M0XHViOTdjIFx1YzIxOFx1ZDU4OVx1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBuXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmx0Oz0gbiAmbHQ7PSAxMDAsMDAwKTxcL3A+XHJcblxyXG48cD5cdWI0NTAgXHViYzg4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBuXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMCBcdWFjNzhcdWNjZDAgXHVhYzAxIFx1YzgxMFx1YzVkMCBcdWIzMDBcdWQ1NWMgXHVjODE1XHViY2Y0IHgsIHksIGNcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiB4LCB5XHViMjk0IFx1YzgxNVx1YzIxOFx1Yzc3NFx1YmE3MCBcdWM4MDhcdWIzMTNcdWFjMTJcdWM3NzQgMSwwMDAsMDAwLDAwMFx1Yzc0NCBcdWIxMThcdWM5YzAgXHVjNTRhXHVhY2UwLCBjXHViMjk0IFkgXHViNjEwXHViMjk0IE5cdWM3NzggXHViYjM4XHVjNzkwXHVjNzc0XHViMmU0LiBZXHViMjk0IFx1Yzc3NCBcdWM4MTBcdWM3NzQgXHViY2ZjXHViODVkIFx1YWVjZFx1YzljOFx1YzVkMCBcdWMxOGRcdWQ1NzRcdWM3ODhcdWM3NGNcdWM3NDQsIE5cdWM3NzRcdWJhNzQgXHVjNTQ0XHViMmQ4XHVjNzQ0IFx1Yzc1OFx1YmJmOFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjOTExXHViY2Y1XHViNDE4XHViMjk0IFx1YzgxMFx1Yzc0MCBcdWM1YzZcdWM3M2NcdWJhNzAsIFx1YmFhOFx1YjRlMCBcdWM4MTBcdWM3NzQgXHVkNTVjIFx1YzljMVx1YzEyMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiIFx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViY2ZjXHViODVkIFx1YWVjZFx1YzljOFx1Yzc0NCBcdWM3NzRcdWI4ZThcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YzViNFx1YzExYyBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWFkZjggXHVjODEwXHViNGU0XHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1Yjk3YyB4IHkgXHVkNjE1XHVkMGRjXHViODVjIFx1Y2Q5Y1x1YjgyNVx1ZDU1OFx1YjI5NFx1YjM3MCwgXHVjNzc0IFx1YzgxMFx1YjRlNFx1Yzc0MCBcdWJjMThcdWMyZGNcdWFjYzQgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM1N2MgXHVkNTVjXHViMmU0LiBcdWNjYWIgXHViYzg4XHVjOWY4IFx1Yzg4Y1x1ZDQ1Y1x1YjI5NCB4XHVjODhjXHVkNDVjXHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVjODEwXHVjNzc0XHVjNWI0XHVjNTdjIFx1ZDU1OFx1YmE3MCwgXHViOWNjXHVjNTdkIFx1YWRmOFx1YjdmMCBcdWM4OGNcdWQ0NWNcdWFjMDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yjc3Y1x1YmE3NCBcdWFkZjggXHVjOTExXHVjNWQwXHVjMTFjIHlcdWM4OGNcdWQ0NWNcdWFjMDAgXHVhYzAwXHVjN2E1IFx1Yzc5MVx1Yzc0MCBcdWM4MTBcdWM3NDQgXHVjMTIwXHVkMGRkXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQxODEiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDb252ZXggSHVsbCIsImRlc2NyaXB0aW9uIjoiPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzMlwvY29udmV4LnBuZ1wiIHN0eWxlPVwiZmxvYXQ6cmlnaHQ7IGhlaWdodDoyMTBweDsgd2lkdGg6MjgwcHhcIiBcLz5GaW5kaW5nIHRoZSBjb252ZXggaHVsbCBvZiBhIHNldCBvZiBwb2ludHMgaXMgYW4gaW1wb3J0YW50IHByb2JsZW0gdGhhdCBpcyBvZnRlbiBwYXJ0IG9mIGEgbGFyZ2VyIHByb2JsZW0uIFRoZXJlIGFyZSBtYW55IGFsZ29yaXRobXMgZm9yIGZpbmRpbmcgdGhlIGNvbnZleCBodWxsLiBTaW5jZSBwcm9ibGVtcyBpbnZvbHZpbmcgdGhlIGNvbnZleCBodWxsIHNvbWV0aW1lcyBhcHBlYXIgaW4gdGhlIEFDTSBXb3JsZCBGaW5hbHMsIGl0IGlzIGEgZ29vZCBpZGVhIGZvciBjb250ZXN0YW50cyB0byBrbm93IHNvbWUgb2YgdGhlc2UgYWxnb3JpdGhtcy48XC9wPlxyXG5cclxuPHA+RmluZGluZyB0aGUgY29udmV4IGh1bGwgb2YgYSBzZXQgb2YgcG9pbnRzIGluIHRoZSBwbGFuZSBjYW4gYmUgZGl2aWRlZCBpbnRvIHR3byBzdWItdGFza3MuIEZpcnN0LCBnaXZlbiBhIHNldCBvZiBwb2ludHMsIGZpbmQgYSBzdWJzZXQgb2YgdGhvc2UgcG9pbnRzIHRoYXQsIHdoZW4gam9pbmVkIHdpdGggbGluZSBzZWdtZW50cywgZm9ybSBhIGNvbnZleCBwb2x5Z29uIHRoYXQgZW5jbG9zZXMgYWxsIG9mIHRoZSBvcmlnaW5hbCBwb2ludHMuIFNlY29uZCwgb3V0cHV0IHRoZSBwb2ludHMgb2YgdGhlIGNvbnZleCBodWxsIGluIG9yZGVyLCB3YWxraW5nIGNvdW50ZXItY2xvY2t3aXNlIGFyb3VuZCB0aGUgcG9seWdvbi4gSW4gdGhpcyBwcm9ibGVtLCB0aGUgZmlyc3Qgc3ViLXRhc2sgaGFzIGFscmVhZHkgYmVlbiBkb25lIGZvciB5b3UsIGFuZCB5b3VyIHByb2dyYW0gc2hvdWxkIGNvbXBsZXRlIHRoZSBzZWNvbmQgc3ViLXRhc2suIFRoYXQgaXMsIGdpdmVuIHRoZSBwb2ludHMgdGhhdCBhcmUga25vd24gdG8gbGllIG9uIHRoZSBjb252ZXggaHVsbCwgb3V0cHV0IHRoZW0gaW4gb3JkZXIgd2Fsa2luZyBjb3VudGVyLWNsb2Nrd2lzZSBhcm91bmQgdGhlIGh1bGwuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBhIHNpbmdsZSBpbnRlZ2VyIDMgJmx0Oz0gbiAmbHQ7PSAxMDAwMDAsIHRoZSBudW1iZXIgb2YgcG9pbnRzLiBUaGUgZm9sbG93aW5nIG4gbGluZXMgb2YgaW5wdXQgZWFjaCBkZXNjcmliZSBhIHBvaW50LiBFYWNoIG9mIHRoZXNlIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBhbmQgZWl0aGVyIGEgWSBvciBhbiBOLCBzZXBhcmF0ZWQgYnkgc3BhY2VzLiBUaGUgdHdvIGludGVnZXJzIHNwZWNpZnkgdGhlIHgtIGFuZCB5LWNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludC4gQSBZIGluZGljYXRlcyB0aGF0IHRoZSBwb2ludCBpcyBvbiB0aGUgY29udmV4IGh1bGwgb2YgYWxsIHRoZSBwb2ludHMsIGFuZCBhIE4gaW5kaWNhdGVzIHRoYXQgaXQgaXMgbm90LiBUaGUgeC0gYW5kIHktY29vcmRpbmF0ZXMgb2YgZWFjaCBwb2ludCB3aWxsIGJlIG5vIGxlc3MgdGhhbiAtMTAwMDAwMDAwMCBhbmQgbm8gZ3JlYXRlciB0aGFuIDEwMDAwMDAwMDAuIE5vIHBvaW50IHdpbGwgYXBwZWFyIG1vcmUgdGhhbiBvbmNlIGluIHRoZSBpbnB1dC4gVGhlIHBvaW50cyBpbiB0aGUgaW5wdXQgd2lsbCBuZXZlciBhbGwgbGllIG9uIGEgbGluZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5GaXJzdCwgb3V0cHV0IGEgbGluZSBjb250YWluaW5nIGEgc2luZ2xlIGludGVnZXIgbSwgdGhlIG51bWJlciBvZiBwb2ludHMgb24gdGhlIGNvbnZleCBodWxsLiBOZXh0IG91dHB1dCBtIGxpbmVzLCBlYWNoIGRlc2NyaWJpbmcgYSBwb2ludCBvbiB0aGUgY29udmV4IGh1bGwsIGluIGNvdW50ZXItY2xvY2t3aXNlIG9yZGVyIGFyb3VuZCB0aGUgaHVsbC4gRWFjaCBvZiB0aGVzZSBsaW5lcyBzaG91bGQgY29udGFpbiB0aGUgeC1jb29yZGluYXRlIG9mIHRoZSBwb2ludCwgZm9sbG93ZWQgYnkgYSBzcGFjZSwgZm9sbG93ZWQgYnkgdGhlIHktY29vcmRpbmF0ZSBvZiB0aGUgcG9pbnQuIFN0YXJ0IHdpdGggdGhlIHBvaW50IG9uIHRoZSBodWxsIHdob3NlIHgtY29vcmRpbmF0ZSBpcyBtaW5pbWFsLiBJZiB0aGVyZSBhcmUgbXVsdGlwbGUgc3VjaCBwb2ludHMsIHN0YXJ0IHdpdGggdGhlIG9uZSB3aG9zZSB5LWNvb3JkaW5hdGUgaXMgbWluaW1hbC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

Contest > Waterloo's local Programming Contests > 13 June, 2009 D번

  • 문제를 번역한 사람: kks227