시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 31 11 10 55.556%

문제

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.999 ≤ 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
W3sicHJvYmxlbV9pZCI6IjQ5OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWFjZmMgXHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHR4eVx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NFx1YjU0YywgXHViYzE4XHVjOWMwXHViOTg0XHVjNzU4IFx1YWUzOFx1Yzc3NFx1YWMwMCAxXHVjNzc4IFx1YzZkMFx1YzczY1x1Yjg1YyBcdWM4MTBcdWM3NDQgXHVjZDVjXHViMzAwIFx1YmE4NyBcdWFjMWMgXHVkM2VjXHVkNTY4XHVjMmRjXHVkMGFjIFx1YzIxOCBcdWM3ODhcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzgxMFx1Yzc3NCBcdWM2ZDBcdWM3NTggXHViMGI0XHViZDgwXHVjNWQwIFx1Yzc4OFx1YWM3MFx1YjA5OCwgXHVjNmQwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWM3NDQgXHViNTRjXHViOTdjIFx1YzZkMFx1Yzc3NCBcdWM4MTBcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2NucC5naWZcIiBzdHlsZT1cIndpZHRoOiA0OTNweDsgaGVpZ2h0OiA0NzJweDtcIiBcLz48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1YWMxY1x1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gXHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBOXHVhYzFjXHVjNzU4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM4MTBcdWM3NTggXHVjODhjXHVkNDVjXHVhYzAwIFx1YzE4Y1x1YzIxOFx1YzgxMCBcdWIyZTRcdWMxMmZcdWM5ZjhcdWM3OTBcdWI5YWNcdWFlNGNcdWM5YzAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gMSAmbGU7IE4gJmxlOyAzMDAsIDAgJmxlOyBYLCBZICZsZTsgMTAuMCBcdWI0NTAgXHVjODEwXHVjNzU4IFx1YWM3MFx1YjlhY1x1YWMwMCAwLjAwMDFcdWJjZjRcdWIyZTQgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNiZFx1YzZiMFx1YjI5NCBcdWM1YzZcdWIyZTQuIFx1YjYxMCwgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgMi4wXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWM2XHViMmU0LiBcdWM5ODksIFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjXHViOTdjIGRcdWI3N2NcdWFjZTAgXHVkNTg4XHVjNzQ0IFx1YjU0YywgMS45OTkgJmxlOyBkICZsZTsgMi4wMDAxXHVjNzQ0IFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWI0NTAgXHVjODEwXHVjNzQwIFx1YzVjNlx1YjJlNC4gXHViOWM4XHVjOWMwXHViOWM5XHVjNzNjXHViODVjLCBcdWMxMzggXHVjODEwXHVjNzc0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCAxXHVjNzc4IFx1YzZkMFx1YzVkMCBcdWIzZDlcdWMyZGNcdWM1ZDAgXHVhYzAwXHVhZTRjXHVjNmI0IFx1YWNiZFx1YzZiMFx1YjNjNCBcdWM1YzZcdWIyZTQuIFx1Yzk4OSwgXHVjMTM4IFx1YzgxMFx1Yzc0NCBQMSwgUDIsIFAzXHViNzdjIFx1ZDU1OFx1YWNlMCwgXHVhYzAxXHVhYzAxXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBkMSwgZDIsIGQzXHViNzdjIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIDAuOTk5ICZsZTsgZGkgJmxlOyAxLjAwMDFcdWM3NDQgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YjljY1x1Yzg3MVx1ZDU1OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNWQwIFx1YjMwMFx1ZDU3NFx1YzExYywgXHVhYzAwXHVjN2E1IFx1YjljZVx1Yzc0MCBcdWM4MTBcdWM3NDQgXHVkM2VjXHVkNTY4XHVkNTU4XHViMjk0IFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc3NCAxXHVjNzc4IFx1YzZkMCBcdWM1NDhcdWM1ZDAgXHVkM2VjXHVkNTY4XHViNDE4XHVjNWI0XHVjNzg4XHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQ5OTUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJDaXJjbGUgYW5kIFBvaW50cyIsImRlc2NyaXB0aW9uIjoiPHA+WW91IGFyZSBnaXZlbiBOIHBvaW50cyBpbiB0aGUgeHktcGxhbmUuIFlvdSBoYXZlIGEgY2lyY2xlIG9mIHJhZGl1cyBvbmUgYW5kIG1vdmUgaXQgb24gdGhlIHh5LXBsYW5lLCBzbyBhcyB0byBlbmNsb3NlIGFzIG1hbnkgb2YgdGhlIHBvaW50cyBhcyBwb3NzaWJsZS4gRmluZCBob3cgbWFueSBwb2ludHMgY2FuIGJlIHNpbXVsdGFuZW91c2x5IGVuY2xvc2VkIGF0IHRoZSBtYXhpbXVtLiBBIHBvaW50IGlzIGNvbnNpZGVyZWQgZW5jbG9zZWQgYnkgYSBjaXJjbGUgd2hlbiBpdCBpcyBpbnNpZGUgb3Igb24gdGhlIGNpcmNsZS48XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbnAuZ2lmXCIgc3R5bGU9XCJoZWlnaHQ6NDcycHg7IHdpZHRoOjQ5M3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkZpZyAxLiBDaXJjbGUgYW5kIFBvaW50czxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGNvbnNpc3RzIG9mIGEgc2VyaWVzIG9mIGRhdGEgc2V0cywgZm9sbG93ZWQgYnkgYSBzaW5nbGUgbGluZSBvbmx5IGNvbnRhaW5pbmcgYSBzaW5nbGUgY2hhcmFjdGVyICYjMzk7MCYjMzk7LCB3aGljaCBpbmRpY2F0ZXMgdGhlIGVuZCBvZiB0aGUgaW5wdXQuIEVhY2ggZGF0YSBzZXQgYmVnaW5zIHdpdGggYSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBOLCB3aGljaCBpbmRpY2F0ZXMgdGhlIG51bWJlciBvZiBwb2ludHMgaW4gdGhlIGRhdGEgc2V0LiBJdCBpcyBmb2xsb3dlZCBieSBOIGxpbmVzIGRlc2NyaWJpbmcgdGhlIGNvb3JkaW5hdGVzIG9mIHRoZSBwb2ludHMuIEVhY2ggb2YgdGhlIE4gbGluZXMgaGFzIHR3byBkZWNpbWFsIGZyYWN0aW9ucyBYIGFuZCBZLCBkZXNjcmliaW5nIHRoZSB4LSBhbmQgeS1jb29yZGluYXRlcyBvZiBhIHBvaW50LCByZXNwZWN0aXZlbHkuIFRoZXkgYXJlIGdpdmVuIHdpdGggZml2ZSBkaWdpdHMgYWZ0ZXIgdGhlIGRlY2ltYWwgcG9pbnQuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgYXNzdW1lIDEgJmx0Oz0gTiAmbHQ7PSAzMDAsIDAuMCAmbHQ7PSBYICZsdDs9IDEwLjAsIGFuZCAwLjAgJmx0Oz0gWSAmbHQ7PSAxMC4wLiBObyB0d28gcG9pbnRzIGFyZSBjbG9zZXIgdGhhbiAwLjAwMDEuIE5vIHR3byBwb2ludHMgaW4gYSBkYXRhIHNldCBhcmUgYXBwcm94aW1hdGVseSBhdCBhIGRpc3RhbmNlIG9mIDIuMC4gTW9yZSBwcmVjaXNlbHksIGZvciBhbnkgdHdvIHBvaW50cyBpbiBhIGRhdGEgc2V0LCB0aGUgZGlzdGFuY2UgZCBiZXR3ZWVuIHRoZSB0d28gbmV2ZXIgc2F0aXNmaWVzIDEuOTk5OSAmbHQ7PSBkICZsdDs9IDIuMDAwMS4gRmluYWxseSwgbm8gdGhyZWUgcG9pbnRzIGluIGEgZGF0YSBzZXQgYXJlIHNpbXVsdGFuZW91c2x5IHZlcnkgY2xvc2UgdG8gYSBzaW5nbGUgY2lyY2xlIG9mIHJhZGl1cyBvbmUuIE1vcmUgcHJlY2lzZWx5LCBsZXQgUDEsIFAyLCBhbmQgUDMgYmUgYW55IHRocmVlIHBvaW50cyBpbiBhIGRhdGEgc2V0LCBhbmQgZDEsIGQyLCBhbmQgZDMgdGhlIGRpc3RhbmNlcyBmcm9tIGFuIGFyYml0cmFyaWx5IHNlbGVjdGVkIHBvaW50IGluIHRoZSB4eS1wbGFuZSB0byBlYWNoIG9mIHRoZW0gcmVzcGVjdGl2ZWx5LiBUaGVuIGl0IG5ldmVyIHNpbXVsdGFuZW91c2x5IGhvbGRzIHRoYXQgMC45OTk5ICZsdDs9IGRpICZsdDs9IDEuMDAwMSAoaSA9IDEsIDIsIDMpLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIGRhdGEgc2V0LCBwcmludCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG1heGltdW0gbnVtYmVyIG9mIHBvaW50cyBpbiB0aGUgZGF0YSBzZXQgdGhhdCBjYW4gYmUgc2ltdWx0YW5lb3VzbHkgZW5jbG9zZWQgYnkgYSBjaXJjbGUgb2YgcmFkaXVzIG9uZS4gTm8gb3RoZXIgY2hhcmFjdGVycyBpbmNsdWRpbmcgbGVhZGluZyBhbmQgdHJhaWxpbmcgc3BhY2VzIHNob3VsZCBiZSBwcmludGVkLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==