시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 66 14 12 32.432%

문제

직각 다각형의 모든 꼭지점이 주어졌을 때, 모든 변을 구하는 프로그램을 작성하시오.

직각다각형의 모든 변은 X축 또는 Y축에 평행한다. 따라서, 모든 각의 크기는 90도 또는 270도이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 꼭지점의 수 N (1 ≤ N ≤ 1000)이 주어진다. 다음 N개 줄에는 각 꼭지점의 좌표 Xi와 Yi가 주어진다. (|Xi|, |Yi| ≤ 10,000)

두 꼭지점이 같은 좌표를 가지는 경우는 없다. 또, 입력으로 주어지는 다각형은 항상 존재하며 닫혀있고, 두 변이 교차하거나 접하는 경우는 없다. (인접한 변 제외) 마지막으로, 다각형 내부에 구멍이 나 있는 경우도 없다. 즉, 다각형은 항상 닫힌 직선으로 이루어져 있다. 입력으로 주어지는 꼭지점의 순서는 무작위이다.

각 테스트 케이스는 빈 줄로 구분되어 있으며, 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스마다 N글자를 공백없이 출력한다. 출력하는 글자는 모두 대문자이며, 각각의 변을 나타낸다. "N"은 북쪽, "E"는 동쪽, "W"는 서쪽, "S"는 서쪽으로 나타내며, 첫 번째로 주어진 꼭지점부터 시계방향으로 출력한다.

예제 입력 1

4
0 0
2 2
0 2
2 0

6
1 1
2 2
0 1
1 0
0 2
2 0

0

예제 출력 1

NESW
WNESWN

힌트

문제에서 주어진 그림은 두 번째 예제이다.

W3sicHJvYmxlbV9pZCI6IjM0NDIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM5YzFcdWFjMDEgXHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzFcdWFjMDEgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NzQgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YmNjMFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ycC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzVweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+XHVjOWMxXHVhYzAxXHViMmU0XHVhYzAxXHVkNjE1XHVjNzU4IFx1YmFhOFx1YjRlMCBcdWJjYzBcdWM3NDAgWFx1Y2Q5NSBcdWI2MTBcdWIyOTQgWVx1Y2Q5NVx1YzVkMCBcdWQzYzlcdWQ1ODlcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViYWE4XHViNGUwIFx1YWMwMVx1Yzc1OCBcdWQwNmNcdWFlMzBcdWIyOTQgOTBcdWIzYzQgXHViNjEwXHViMjk0IDI3MFx1YjNjNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzFjXHVjNzU4IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM3NTggXHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVjMjE4IE4gKDEgJmxlOyBOICZsZTsgMTAwMClcdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc1OCBcdWM4OGNcdWQ0NWMgWDxzdWI+aTxcL3N1Yj5cdWM2NDAgWTxzdWI+aTxcL3N1Yj5cdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAofFg8c3ViPmk8XC9zdWI+fCwgfFk8c3ViPmk8XC9zdWI+fCAmbGU7IDEwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViNDUwIFx1YWYyZFx1YzljMFx1YzgxMFx1Yzc3NCBcdWFjMTlcdWM3NDAgXHVjODhjXHVkNDVjXHViOTdjIFx1YWMwMFx1YzljMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1ZDU2ZFx1YzBjMSBcdWM4NzRcdWM3YWNcdWQ1NThcdWJhNzAgXHViMmViXHVkNjAwXHVjNzg4XHVhY2UwLCBcdWI0NTAgXHViY2MwXHVjNzc0IFx1YWQ1MFx1Y2MyOFx1ZDU1OFx1YWM3MFx1YjA5OCBcdWM4MTFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC4gKFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWJjYzAgXHVjODFjXHVjNjc4KSBcdWI5YzhcdWM5YzBcdWI5YzlcdWM3M2NcdWI4NWMsIFx1YjJlNFx1YWMwMVx1ZDYxNSBcdWIwYjRcdWJkODBcdWM1ZDAgXHVhZDZjXHViYTRkXHVjNzc0IFx1YjA5OCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC4gXHVjOTg5LCBcdWIyZTRcdWFjMDFcdWQ2MTVcdWM3NDAgXHVkNTZkXHVjMGMxIFx1YjJlYlx1ZDc4YyBcdWM5YzFcdWMxMjBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljMFx1YjI5NCBcdWFmMmRcdWM5YzBcdWM4MTBcdWM3NTggXHVjMjFjXHVjMTFjXHViMjk0IFx1YmIzNFx1Yzc5MVx1YzcwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWIyOTQgXHViZTQ4IFx1YzkwNFx1Yjg1YyBcdWFkNmNcdWJkODRcdWI0MThcdWM1YjQgXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5YzhcdWIyZTQgTlx1YWUwMFx1Yzc5MFx1Yjk3YyBcdWFjZjVcdWJjMzFcdWM1YzZcdWM3NzQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWNkOWNcdWI4MjVcdWQ1NThcdWIyOTQgXHVhZTAwXHVjNzkwXHViMjk0IFx1YmFhOFx1YjQ1MCBcdWIzMDBcdWJiMzhcdWM3OTBcdWM3NzRcdWJhNzAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWJjYzBcdWM3NDQgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiAmcXVvdDtOJnF1b3Q7XHVjNzQwIFx1YmQ4MVx1Y2FiZCwgJnF1b3Q7RSZxdW90O1x1YjI5NCBcdWIzZDlcdWNhYmQsICZxdW90O1cmcXVvdDtcdWIyOTQgXHVjMTFjXHVjYWJkLCAmcXVvdDtTJnF1b3Q7XHViMjk0IFx1YzExY1x1Y2FiZFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjRcdWJhNzAsIFx1Y2NhYiBcdWJjODhcdWM5ZjhcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWYyZFx1YzljMFx1YzgxMFx1YmQ4MFx1ZDEzMCBcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWJiMzhcdWM4MWNcdWM1ZDBcdWMxMWMgXHVjOGZjXHVjNWI0XHVjOWM0IFx1YWRmOFx1YjliY1x1Yzc0MCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzYwOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM0NDIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWN0YW5ndWxhciBQb2x5Z29ucyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gdGhpcyBwcm9ibGVtLCB3ZSB3aWxsIGhlbHAgdGhlIEZhY3VsdHkgb2YgQ2l2aWwgRW5naW5lZXJpbmcuIFRoZXkgbmVlZCBhIHNvZnR3YXJlIHRvIGFuYWx5emUgZ3JvdW5kIHBsYW5zIG9mIGJ1aWxkaW5ncy4gU3BlY2lcdWZiMDFjYWxseSwgeW91ciB0YXNrIGlzIHRvIGRldGVjdCBvdXRsaW5lcyBvZiBhIGJ1aWxkaW5nIHdoZW4gYWxsIG9mIGl0cyBjb3JuZXJzIGFyZSBnaXZlbi48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9ycC5wbmdcIiBzdHlsZT1cImhlaWdodDoxMzVweDsgd2lkdGg6NTA2cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+WW91IG1heSBhc3N1bWUgdGhhdCBlYWNoIGJ1aWxkaW5nIGlzIGEgcmVjdGFuZ3VsYXIgcG9seWdvbiB3aXRoIGVhY2ggb2YgaXRzIHNpZGVzIGJlaW5nIHBhcmFsbGVsIGVpdGhlciB3aXRoIFggb3IgWSBheGlzLiBUaGVyZWZvcmUsIGVhY2ggb2YgaXRzIHZlcnRleCBhbmdsZXMgaXMgZXhhY3RseSBlaXRoZXIgOTAgb3IgMjcwIGRlZ3JlZXMuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgY29udGFpbnMgc2V2ZXJhbCBidWlsZGluZ3MuIFRoZSBkZXNjcmlwdGlvbiBvZiBlYWNoIGJ1aWxkaW5nIHN0YXJ0cyB3aXRoIGEgc2luZ2xlIHBvc2l0aXZlIGludGVnZXIgTiwgdGhlIG51bWJlciBvZiBjb3JuZXJzIChwb2x5Z29uIHZlcnRpY2VzKSwgMSAmbGU7IE4gJmxlOyAxMDAwLiBUaGVuIHRoZXJlIGFyZSBOIHBhaXJzIG9mIGludGVnZXIgbnVtYmVycyBYPHN1Yj5pPFwvc3ViPiwgWTxzdWI+aTxcL3N1Yj4gZ2l2aW5nIGNvb3JkaW5hdGVzIG9mIGluZGl2aWR1YWwgY29ybmVycywgfFg8c3ViPmk8XC9zdWI+fCx8WTxzdWI+aTxcL3N1Yj58ICZsZTsgMTAgMDAwLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSB0aGF0IGFsbCBjb3JuZXJzIGFyZSBsaXN0ZWQgYW5kIG5vIHR3byBvZiB0aGVtIGhhdmUgdGhlIHNhbWUgY29vcmRpbmF0ZXMuIFRoZSBwb2x5Z29uIGRvZXMgYWx3YXlzIGV4aXN0LCBpdCBpcyBjbG9zZWQsIGl0cyBzaWRlcyBkbyBub3QgaW50ZXJzZWN0IG9yIHRvdWNoIChleGNlcHQgbmVpZ2hib3Jpbmcgc2lkZXMsIG9mIGNvdXJzZSksIGFuZCBpdCBjb250YWlucyBubyAmbGRxdW87aG9sZXMmcmRxdW87IGluc2lkZS4gSW4gb3RoZXIgd29yZHMsIHRoZSBvdXRsaW5lIGlzIGZvcm1lZCBieSBvbmUgY2xvc2VkIGxpbmUuIFRoZSBvcmRlciBvZiBjb3JuZXJzIGluIHRoZSBpbnB1dCBcdWZiMDFsZSBtYXkgYmUgYXJiaXRyYXJ5LjxcL3A+XHJcblxyXG48cD5UaGVyZSBpcyBhbiBlbXB0eSBsaW5lIGFmdGVyIGVhY2ggYnVpbGRpbmcsIHRoZW4gdGhlIG5leHQgb25lIGlzIGRlc2NyaWJlZC4gQWZ0ZXIgdGhlIGxhc3QgYnVpbGRpbmcsIHRoZXJlIGlzIGEgc2luZ2xlIHplcm8gdGhhdCBzaWduYWxzIHRoZSBlbmQgb2YgaW5wdXQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggYnVpbGRpbmcsIG91dHB1dCBvbmUgbGluZSBjb250YWluaW5nIE4gY2hhcmFjdGVycyB3aXRob3V0IGFueSB3aGl0ZXNwYWNlIGJldHdlZW4gdGhlbS4gVGhlIGNoYXJhY3RlcnMgc2hvdWxkIGJlIHVwcGVyY2FzZSBsZXR0ZXJzIHRoYXQgc3BlY2lmeSBkaXJlY3Rpb25zIG9mIGluZGl2aWR1YWwgd2FsbHMgKHNpZGVzKSB3aGVuIHRoZSBidWlsZGluZyBvdXRsaW5lIGlzIGZvbGxvd2VkLiAmbGRxdW87TiZyZHF1bzsgc3RhbmRzIGZvciBOb3J0aCAodGhlIHBvc2l0aXZlIGRpcmVjdGlvbiBvZiB0aGUgWSBheGlzKSwgJmxkcXVvO0UmcmRxdW87IGZvciBFYXN0ICh0aGUgcG9zaXRpdmUgZGlyZWN0aW9uIG9mIHRoZSBYIGF4aXMpLCAmbGRxdW87VyZyZHF1bzsgZm9yIFdlc3QsIGFuZCAmbGRxdW87UyZyZHF1bzsgZm9yIFNvdXRoLiBUaGUgJmxkcXVvO3dhbGsmcmRxdW87IHNob3VsZCBzdGFydCBpbiB0aGUgdmVydGV4IHRoYXQgaGFzIGJlZW4gZ2l2ZW4gXHVmYjAxcnN0IGluIHRoZSBpbnB1dCBhbmQgYWx3YXlzIHByb2NlZWQgaW4gdGhlIGNsb2Nrd2lzZSBkaXJlY3Rpb24uPFwvcD5cclxuIiwiaGludCI6IjxwPlRoZSBzZWNvbmQgc2FtcGxlIGlucHV0IGNvcnJlc3BvbmRzIHRvIHRoZSBwaWN0dXJlLjxcL3A+XHJcbiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

ACM-ICPC > Regionals > Europe > Central European Regional Contest > CERC 2007 P번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: pichulia
  • 문제의 오타를 찾은 사람: skdudn321