시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB145563838.384%

문제

xy평면에 N개의 점이 있다. 이때, 반지름의 길이가 1인 원으로 점을 최대 몇 개 포함시킬 수 있는지 구하는 프로그램을 작성하시오. 점이 원의 내부에 있거나, 원 위에 있을 때를 원이 점을 포함하는 것이다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 점의 개수 N이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 소수점 다섯째자리까지 주어진다.

입력의 마지막 줄에는 0이 주어진다. 1 ≤ N ≤ 300, 0 ≤ X, Y ≤ 10.0 두 점의 거리가 0.0001보다 가까운 경우는 없다. 또, 두 점의 거리가 2.0에 가까운 경우도 없다. 즉, 두 점의 거리를 d라고 했을 때, 1.999 ≤ d ≤ 2.0001을 만족하는 두 점은 없다. 마지막으로, 세 점이 반지름이 1인 원에 동시에 가까운 경우도 없다. 즉, 세 점을 P1, P2, P3라 하고, 각각의 거리를 d1, d2, d3라 했을 때, 0.9999 ≤ di ≤ 1.0001을 동시에 만족하는 경우도 없다.

출력

각 테스트 케이스에 대해서, 가장 많은 점을 포함하는 반지름이 1인 원 안에 포함되어있는 점의 개수를 출력한다.

예제 입력 1

3
6.47634 7.69628
5.16828 4.79915
6.69533 6.20378
6
7.15296 4.08328
6.50827 2.69466
5.91219 3.86661
5.29853 4.16097
6.10838 3.46039
6.34060 2.41599
8
7.90650 4.01746
4.10998 4.18354
4.67289 4.01887
6.33885 4.28388
4.98106 3.82728
5.12379 5.16473
7.84664 4.67693
4.02776 3.87990
20
6.65128 5.47490
6.42743 6.26189
6.35864 4.61611
6.59020 4.54228
4.43967 5.70059
4.38226 5.70536
5.50755 6.18163
7.41971 6.13668
6.71936 3.04496
5.61832 4.23857
5.99424 4.29328
5.60961 4.32998
6.82242 5.79683
5.44693 3.82724
6.70906 3.65736
7.89087 5.68000
6.23300 4.59530
5.92401 4.92329
6.24168 3.81389
6.22671 3.62210
0

예제 출력 1

2
5
5
11
W3sicHJvYmxlbV9pZCI6IjQ5OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWFjZmMgXHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD54eVx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYzE4XHVjOWMwXHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWM4MTBcdWM3NDQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWMgXHVkM2VjXHVkNTY4XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzgxMFx1Yzc3NCBcdWM2ZDBcdWM3NTggXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1YWM3MFx1YjA5OCwgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViOTdjIFx1YzZkMFx1Yzc3NCBcdWM4MTBcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbnAuZ2lmXCIgc3R5bGU9XCJ3aWR0aDogNDkzcHg7IGhlaWdodDogNDcycHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWIyZTRcdWMxMmZcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMSAmbGU7IE4gJmxlOyAzMDAsIDAgJmxlOyBYLCBZICZsZTsgMTAuMCBcdWI0NTAgXHVjODEwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCAwLjAwMDFcdWJjZjRcdWIyZTQgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgMi4wXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWM2XHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIGRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgMS45OTkgJmxlOyBkICZsZTsgMi4wMDAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODEwXHVjNzQwIFx1YzVjNlx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWMxMzggXHVjODEwXHVjNzc0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCAxXHVjNzc4IFx1YzZkMFx1YzVkMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVjMTM4IFx1YzgxMFx1Yzc0NCBQPHN1Yj4xPFwvc3ViPiwgUDxzdWI+MjxcL3N1Yj4sIFA8c3ViPjM8XC9zdWI+XHViNzdjIFx1ZDU1OFx1YWNlMCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBkPHN1Yj4xPFwvc3ViPiwgZDxzdWI+MjxcL3N1Yj4sIGQ8c3ViPjM8XC9zdWI+XHViNzdjIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIDAuOTk5OSAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMS4wMDAxXHVjNzQ0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjODEwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMVx1Yzc3OCBcdWM2ZDAgXHVjNTQ4XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0OTk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2lyY2xlIGFuZCBQb2ludHMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gTiBwb2ludHMgaW4gdGhlIHh5LXBsYW5lLiBZb3UgaGF2ZSBhIGNpcmNsZSBvZiByYWRpdXMgb25lIGFuZCBtb3ZlIGl0IG9uIHRoZSB4eS1wbGFuZSwgc28gYXMgdG8gZW5jbG9zZSBhcyBtYW55IG9mIHRoZSBwb2ludHMgYXMgcG9zc2libGUuIEZpbmQgaG93IG1hbnkgcG9pbnRzIGNhbiBiZSBzaW11bHRhbmVvdXNseSBlbmNsb3NlZCBhdCB0aGUgbWF4aW11bS4gQSBwb2ludCBpcyBjb25zaWRlcmVkIGVuY2xvc2VkIGJ5IGEgY2lyY2xlIHdoZW4gaXQgaXMgaW5zaWRlIG9yIG9uIHRoZSBjaXJjbGUuPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY25wLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjQ3MnB4OyB3aWR0aDo0OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5GaWcgMS4gQ2lyY2xlIGFuZCBQb2ludHM8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiBkYXRhIHNldHMsIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIGxpbmUgb25seSBjb250YWluaW5nIGEgc2luZ2xlIGNoYXJhY3RlciAmIzM5OzAmIzM5Oywgd2hpY2ggaW5kaWNhdGVzIHRoZSBlbmQgb2YgdGhlIGlucHV0LiBFYWNoIGRhdGEgc2V0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgTiwgd2hpY2ggaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluIHRoZSBkYXRhIHNldC4gSXQgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcyBkZXNjcmliaW5nIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzLiBFYWNoIG9mIHRoZSBOIGxpbmVzIGhhcyB0d28gZGVjaW1hbCBmcmFjdGlvbnMgWCBhbmQgWSwgZGVzY3JpYmluZyB0aGUgeC0gYW5kIHktY29vcmRpbmF0ZXMgb2YgYSBwb2ludCwgcmVzcGVjdGl2ZWx5LiBUaGV5IGFyZSBnaXZlbiB3aXRoIGZpdmUgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSAxICZsZTsgTiAmbGU7IDMwMCwgMC4wICZsZTsgWCAmbGU7Jm5ic3A7MTAuMCwgYW5kIDAuMCAmbGU7IFkgJmxlOyAxMC4wLiBObyB0d28gcG9pbnRzIGFyZSBjbG9zZXIgdGhhbiAwLjAwMDEuIE5vIHR3byBwb2ludHMgaW4gYSBkYXRhIHNldCBhcmUgYXBwcm94aW1hdGVseSBhdCBhIGRpc3RhbmNlIG9mIDIuMC4gTW9yZSBwcmVjaXNlbHksIGZvciBhbnkgdHdvIHBvaW50cyBpbiBhIGRhdGEgc2V0LCB0aGUgZGlzdGFuY2UgZCBiZXR3ZWVuIHRoZSB0d28gbmV2ZXIgc2F0aXNmaWVzIDEuOTk5OSAmbGU7IGQgJmxlOyAyLjAwMDEuIEZpbmFsbHksIG5vIHRocmVlIHBvaW50cyBpbiBhIGRhdGEgc2V0IGFyZSBzaW11bHRhbmVvdXNseSB2ZXJ5IGNsb3NlIHRvIGEgc2luZ2xlIGNpcmNsZSBvZiByYWRpdXMgb25lLiBNb3JlIHByZWNpc2VseSwgbGV0IFA8c3ViPjE8XC9zdWI+LCBQPHN1Yj4yPFwvc3ViPiwgYW5kIFA8c3ViPjM8XC9zdWI+IGJlIGFueSB0aHJlZSBwb2ludHMgaW4gYSBkYXRhIHNldCwgYW5kIGQ8c3ViPjE8XC9zdWI+LCBkPHN1Yj4yPFwvc3ViPiwgYW5kIGQ8c3ViPjM8XC9zdWI+IHRoZSBkaXN0YW5jZXMgZnJvbSBhbiBhcmJpdHJhcmlseSBzZWxlY3RlZCBwb2ludCBpbiB0aGUgeHktcGxhbmUgdG8gZWFjaCBvZiB0aGVtIHJlc3BlY3RpdmVseS4gVGhlbiBpdCBuZXZlciBzaW11bHRhbmVvdXNseSBob2xkcyB0aGF0IDAuOTk5OSAmbGU7IGQ8c3ViPmk8XC9zdWI+ICZsZTsgMS4wMDAxIChpID0gMSwgMiwgMykuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggZGF0YSBzZXQsIHByaW50IGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgbWF4aW11bSBudW1iZXIgb2YgcG9pbnRzIGluIHRoZSBkYXRhIHNldCB0aGF0IGNhbiBiZSBzaW11bHRhbmVvdXNseSBlbmNsb3NlZCBieSBhIGNpcmNsZSBvZiByYWRpdXMgb25lLiBObyBvdGhlciBjaGFyYWN0ZXJzIGluY2x1ZGluZyBsZWFkaW5nIGFuZCB0cmFpbGluZyBzcGFjZXMgc2hvdWxkIGJlIHByaW50ZWQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2004 Japan Domestic Contest D번

  • 문제의 오타를 찾은 사람: leehosu01