시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 55 12 11 27.500%

문제

볼록 정다각형은 변의 길이가 모두 같으면서 내부각의 크기도 같고 그 크기는 180도보다 작다. 정사각형은 볼록 정다각형이다.

볼록 정다각형 R의 세 점이 주어진다. 이 때, R의 점의 개수의 최소값을 구하는 프로그램을 작성하시오.

입력

각 테스트 케이스는 세 줄로 이루어져 있다. 한 줄에 하나씩 볼록 정다각형 R의 한 점 (xi, yi)가 주어진다. (-104 ≤ xi, yi ≤ 104) 좌표의 오차는 10-6이다. (정확한 좌표와의 차이가 최대 10-6) 두 점의 거리는 항상 최소 1이며, R은 최대 1000개의 점으로 이루어져 있다.

입력의 마지막 줄에는 END가 주어진다.

출력

각 테스트 케이스에 대해서 R의 점의 개수의 최소값을 출력한다.

예제 입력 1

-1385.736326 -146.954822
430.000292 -2041.361203
1162.736034 478.316025
0.000000 4147.000000
-4147.000000 0.000000
0.000000 -4147.000000
END

예제 출력 1

3
4

힌트

W3sicHJvYmxlbV9pZCI6IjM4NDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWJjZmNcdWI4NWQgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWJjZmNcdWI4NWQgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1XHVjNzQwIFx1YmNjMFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgXHViYWE4XHViNDUwIFx1YWMxOVx1YzczY1x1YmE3NFx1YzExYyBcdWIwYjRcdWJkODBcdWFjMDFcdWM3NTggXHVkMDZjXHVhZTMwXHViM2M0IFx1YWMxOVx1YWNlMCBcdWFkZjggXHVkMDZjXHVhZTMwXHViMjk0IDE4MFx1YjNjNFx1YmNmNFx1YjJlNCBcdWM3OTFcdWIyZTQuIFx1YzgxNVx1YzBhY1x1YWMwMVx1ZDYxNVx1Yzc0MCBcdWJjZmNcdWI4NWQgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWJjZmNcdWI4NWQgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1IFJcdWM3NTggXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFJcdWM3NTggXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWMxMzggXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YmNmY1x1Yjg1ZCBcdWM4MTVcdWIyZTRcdWFjMDFcdWQ2MTUgUlx1Yzc1OCBcdWQ1NWMgXHVjODEwICh4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4pXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKC0xMDxzdXA+NDxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pIFx1Yzg4Y1x1ZDQ1Y1x1Yzc1OCBcdWM2MjRcdWNjMjhcdWIyOTQgMTA8c3VwPi02PFwvc3VwPlx1Yzc3NFx1YjJlNC4gKFx1YzgxNVx1ZDY1NVx1ZDU1YyBcdWM4OGNcdWQ0NWNcdWM2NDBcdWM3NTggXHVjYzI4XHVjNzc0XHVhYzAwIFx1Y2Q1Y1x1YjMwMCAxMDxzdXA+LTY8XC9zdXA+KSBcdWI0NTAgXHVjODEwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YjI5NCBcdWQ1NmRcdWMwYzEgXHVjZDVjXHVjMThjIDFcdWM3NzRcdWJhNzAsIFJcdWM3NDAgXHVjZDVjXHViMzAwIDEwMDBcdWFjMWNcdWM3NTggXHVjODEwXHVjNzNjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IEVORFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjIFJcdWM3NTggXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOFx1Yzc1OCBcdWNkNWNcdWMxOGNcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM4NDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJSZWd1bGFyIENvbnZleCBQb2x5Z29uIiwiZGVzY3JpcHRpb24iOiI8cD5BIHJlZ3VsYXIgY29udmV4IHBvbHlnb24gaXMgYSBwb2x5Z29uIHdoZXJlIGVhY2ggc2lkZSBoYXMgdGhlIHNhbWUgbGVuZ3RoLCBhbmQgYWxsIGludGVyaW9yIGFuZ2xlcyBhcmUgZXF1YWwgYW5kIGxlc3MgdGhhbiAxODAgZGVncmVlcy4gQSBzcXVhcmUsIGZvciBleGFtcGxlLCBpcyBhIHJlZ3VsYXIgY29udmV4IHBvbHlnb24uIFlvdSBhcmUgZ2l2ZW4gdGhyZWUgcG9pbnRzIHdoaWNoIGFyZSB2ZXJ0aWNlcyBvZiBhIHJlZ3VsYXIgY29udmV4IHBvbHlnb24gUjsgY2FuIHlvdSBkZXRlcm1pbmUgdGhlIG1pbmltdW0gbnVtYmVyIG9mIHZlcnRpY2VzIHRoYXQgUiBtdXN0IGhhdmU/PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5FYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiB0aHJlZSBsaW5lcy4gTGluZSBpIGNvbnNpc3RzIG9mIHR3byBmbG9hdGluZyBwb2ludCB2YWx1ZXMgeDxzdWI+aTxcL3N1Yj4gYW5kIHk8c3ViPmk8XC9zdWI+ICgtMTA8c3VwPjQ8XC9zdXA+ICZsZTsgeDxzdWI+aTxcL3N1Yj4sIHk8c3ViPmk8XC9zdWI+ICZsZTsgMTA8c3VwPjQ8XC9zdXA+KSB3aGVyZSAoeGksIHk8c3ViPmk8XC9zdWI+KSBhcmUgdGhlIGNvb3JkaW5hdGVzIG9mIGEgdmVydGV4IG9mIFIuIFRoZSBjb29yZGluYXRlcyBhcmUgZ2l2ZW4gd2l0aCBhIHByZWNpc2lvbiZuYnNwO29mIDEwPHN1cD42PFwvc3VwPiwgaS5lLiwgdGhleSBkaWZmZXIgZnJvbSB0aGUgZXhhY3QgY29vcmRpbmF0ZXMgYnkgYXQgbW9zdCAxMDxzdXA+NjxcL3N1cD4uIFlvdSBtYXkgYXNzdW1lIHRoYXQgZm9yIGVhY2ggdGVzdCBjYXNlJm5ic3A7dGhlIEV1Y2xpZGVhbiBkaXN0YW5jZSBiZXR3ZWVuIGFueSB0d28gZ2l2ZW4gcG9pbnRzIGlzIGF0IGxlYXN0IDEsIGFuZCBSIGhhcyBhdCBtb3N0IDEwMDAgdmVydGljZXMuIFRoZSZuYnNwO2lucHV0IHdpbGwgZmluaXNoIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgdGhlIHdvcmQgRU5ELjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSwgcHJpbnQgb25lIGxpbmUgd2l0aCB0aGUgbWluaW11bSBudW1iZXIgb2YgdmVydGljZXMgdGhhdCBSIG11c3QgaGF2ZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Southwestern European Regional Contest > SWERC 2011 I번

  • 문제를 번역한 사람: baekjoon
  • 잘못된 조건을 찾은 사람: jh05013