시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 95 16 13 24.074%

문제

볼록 정다각형은 변의 길이가 모두 같으면서 내부각의 크기도 같고 그 크기는 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+XHJcblxyXG48cD5cdWJjZmNcdWI4NWQgXHVjODE1XHViMmU0XHVhYzAxXHVkNjE1IFJcdWM3NTggXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1Yzc3NFx1YjU0YywgUlx1Yzc1OCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViMjk0IFx1YzEzOCBcdWM5MDRcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM1MjkgXHViY2ZjXHViODVkIFx1YzgxNVx1YjJlNFx1YWMwMVx1ZDYxNSBSXHVjNzU4IFx1ZDU1YyBcdWM4MTAgKHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPilcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoLTEwPHN1cD40PFwvc3VwPiAmbGU7IHg8c3ViPmk8XC9zdWI+LCB5PHN1Yj5pPFwvc3ViPiAmbGU7IDEwPHN1cD40PFwvc3VwPikgXHVjODhjXHVkNDVjXHVjNzU4IFx1YzYyNFx1Y2MyOFx1YjI5NCAxMDxzdXA+LTY8XC9zdXA+XHVjNzc0XHViMmU0LiAoXHVjODE1XHVkNjU1XHVkNTVjIFx1Yzg4Y1x1ZDQ1Y1x1YzY0MFx1Yzc1OCBcdWNjMjhcdWM3NzRcdWFjMDAgXHVjZDVjXHViMzAwIDEwPHN1cD4tNjxcL3N1cD4pIFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjXHViMjk0IFx1ZDU2ZFx1YzBjMSBcdWNkNWNcdWMxOGMgMVx1Yzc3NFx1YmE3MCwgUlx1Yzc0MCBcdWNkNWNcdWIzMDAgMTAwMFx1YWMxY1x1Yzc1OCBcdWM4MTBcdWM3M2NcdWI4NWMgXHVjNzc0XHViOGU4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgRU5EXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMgUlx1Yzc1OCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHVjNzU4IFx1Y2Q1Y1x1YzE5Zlx1YWMxMlx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzg0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlJlZ3VsYXIgQ29udmV4IFBvbHlnb24iLCJkZXNjcmlwdGlvbiI6IjxwPkEgcmVndWxhciBjb252ZXggcG9seWdvbiBpcyBhIHBvbHlnb24gd2hlcmUgZWFjaCBzaWRlIGhhcyB0aGUgc2FtZSBsZW5ndGgsIGFuZCBhbGwgaW50ZXJpb3IgYW5nbGVzIGFyZSBlcXVhbCBhbmQgbGVzcyB0aGFuIDE4MCBkZWdyZWVzLiBBIHNxdWFyZSwgZm9yIGV4YW1wbGUsIGlzIGEgcmVndWxhciBjb252ZXggcG9seWdvbi4gWW91IGFyZSBnaXZlbiB0aHJlZSBwb2ludHMgd2hpY2ggYXJlIHZlcnRpY2VzIG9mIGEgcmVndWxhciBjb252ZXggcG9seWdvbiBSOyBjYW4geW91IGRldGVybWluZSB0aGUgbWluaW11bSBudW1iZXIgb2YgdmVydGljZXMgdGhhdCBSIG11c3QgaGF2ZT88XC9wPlxyXG4iLCJpbnB1dCI6IjxwPkVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIHRocmVlIGxpbmVzLiBMaW5lIGkgY29uc2lzdHMgb2YgdHdvIGZsb2F0aW5nIHBvaW50IHZhbHVlcyB4PHN1Yj5pPFwvc3ViPiBhbmQgeTxzdWI+aTxcL3N1Yj4gKC0xMDxzdXA+NDxcL3N1cD4gJmxlOyB4PHN1Yj5pPFwvc3ViPiwgeTxzdWI+aTxcL3N1Yj4gJmxlOyAxMDxzdXA+NDxcL3N1cD4pIHdoZXJlICh4aSwgeTxzdWI+aTxcL3N1Yj4pIGFyZSB0aGUgY29vcmRpbmF0ZXMgb2YgYSB2ZXJ0ZXggb2YgUi4gVGhlIGNvb3JkaW5hdGVzIGFyZSBnaXZlbiB3aXRoIGEgcHJlY2lzaW9uJm5ic3A7b2YgMTA8c3VwPjY8XC9zdXA+LCBpLmUuLCB0aGV5IGRpZmZlciBmcm9tIHRoZSBleGFjdCBjb29yZGluYXRlcyBieSBhdCBtb3N0IDEwPHN1cD42PFwvc3VwPi4gWW91IG1heSBhc3N1bWUgdGhhdCBmb3IgZWFjaCB0ZXN0IGNhc2UmbmJzcDt0aGUgRXVjbGlkZWFuIGRpc3RhbmNlIGJldHdlZW4gYW55IHR3byBnaXZlbiBwb2ludHMgaXMgYXQgbGVhc3QgMSwgYW5kIFIgaGFzIGF0IG1vc3QgMTAwMCB2ZXJ0aWNlcy4gVGhlJm5ic3A7aW5wdXQgd2lsbCBmaW5pc2ggd2l0aCBhIGxpbmUgY29udGFpbmluZyB0aGUgd29yZCBFTkQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlLCBwcmludCBvbmUgbGluZSB3aXRoIHRoZSBtaW5pbXVtIG51bWJlciBvZiB2ZXJ0aWNlcyB0aGF0IFIgbXVzdCBoYXZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==

출처

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

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