시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 18 10 9 52.941%

문제

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

힌트

W3sicHJvYmxlbV9pZCI6IjQ5OTUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2ZDBcdWFjZmMgXHVjODEwIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHR4eVx1ZDNjOVx1YmE3NFx1YzVkMCBOXHVhYzFjXHVjNzU4IFx1YzgxMFx1Yzc3NCBcdWM3ODhcdWIyZTQuIFx1Yzc3NCBcdWI1NGMsIFx1YmMxOFx1YzljMFx1Yjk4NFx1Yzc1OCBcdWFlMzhcdWM3NzRcdWFjMDAgMVx1Yzc3OCBcdWM2ZDBcdWM3M2NcdWI4NWMgXHVjODEwXHVjNzQ0IFx1Y2Q1Y1x1YjMwMCBcdWJhODcgXHVhYzFjIFx1ZDNlY1x1ZDU2OFx1YzJkY1x1ZDBhYyBcdWMyMTggXHVjNzg4XHViMjk0XHVjOWMwIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiBcdWM4MTBcdWM3NzQgXHVjNmQwXHVjNzU4IFx1YjBiNFx1YmQ4MFx1YzVkMCBcdWM3ODhcdWFjNzBcdWIwOTgsIFx1YzZkMCBcdWM3MDRcdWM1ZDAgXHVjNzg4XHVjNzQ0IFx1YjU0Y1x1Yjk3YyBcdWM2ZDBcdWM3NzQgXHVjODEwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWFjODNcdWM3NzRcdWIyZTQuPFwvcD5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9jbnAuZ2lmXCIgc3R5bGU9XCJ3aWR0aDogNDkzcHg7IGhlaWdodDogNDcycHg7XCIgXC8+PFwvcD5cclxuIiwiaW5wdXQiOiJcclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yzc1OCBcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IFx1YzgxMFx1Yzc1OCBcdWFjMWNcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YjQ1OFx1YzlmOCBcdWM5MDRcdWJkODBcdWQxMzAgTlx1YWMxY1x1Yzc1OCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjODEwXHVjNzU4IFx1Yzg4Y1x1ZDQ1Y1x1YWMwMCBcdWMxOGNcdWMyMThcdWM4MTAgXHViMmU0XHVjMTJmXHVjOWY4XHVjNzkwXHViOWFjXHVhZTRjXHVjOWMwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWM5MDRcdWM1ZDBcdWIyOTQgMFx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIDEgJmxlOyBOICZsZTsgMzAwLCAwICZsZTsgWCwgWSAmbGU7IDEwLjAgXHViNDUwIFx1YzgxMFx1Yzc1OCBcdWFjNzBcdWI5YWNcdWFjMDAgMC4wMDAxXHViY2Y0XHViMmU0IFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LiBcdWI2MTAsIFx1YjQ1MCBcdWM4MTBcdWM3NTggXHVhYzcwXHViOWFjXHVhYzAwIDIuMFx1YzVkMCBcdWFjMDBcdWFlNGNcdWM2YjQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC4gXHVjOTg5LCBcdWI0NTAgXHVjODEwXHVjNzU4IFx1YWM3MFx1YjlhY1x1Yjk3YyBkXHViNzdjXHVhY2UwIFx1ZDU4OFx1Yzc0NCBcdWI1NGMsIDEuOTk5ICZsZTsgZCAmbGU7IDIuMDAwMVx1Yzc0NCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHViNDUwIFx1YzgxMFx1Yzc0MCBcdWM1YzZcdWIyZTQuIFx1YjljOFx1YzljMFx1YjljOVx1YzczY1x1Yjg1YywgXHVjMTM4IFx1YzgxMFx1Yzc3NCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMVx1Yzc3OCBcdWM2ZDBcdWM1ZDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWMwMFx1YWU0Y1x1YzZiNCBcdWFjYmRcdWM2YjBcdWIzYzQgXHVjNWM2XHViMmU0LiBcdWM5ODksIFx1YzEzOCBcdWM4MTBcdWM3NDQgUDEsIFAyLCBQM1x1Yjc3YyBcdWQ1NThcdWFjZTAsIFx1YWMwMVx1YWMwMVx1Yzc1OCBcdWFjNzBcdWI5YWNcdWI5N2MgZDEsIGQyLCBkM1x1Yjc3YyBcdWQ1ODhcdWM3NDQgXHViNTRjLCAwLjk5OSAmbGU7IGRpICZsZTsgMS4wMDAxXHVjNzQ0IFx1YjNkOVx1YzJkY1x1YzVkMCBcdWI5Y2NcdWM4NzFcdWQ1NThcdWIyOTQgXHVhY2JkXHVjNmIwXHViM2M0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cclxuXHRcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YzVkMCBcdWIzMDBcdWQ1NzRcdWMxMWMsIFx1YWMwMFx1YzdhNSBcdWI5Y2VcdWM3NDAgXHVjODEwXHVjNzQ0IFx1ZDNlY1x1ZDU2OFx1ZDU1OFx1YjI5NCBcdWJjMThcdWM5YzBcdWI5ODRcdWM3NzQgMVx1Yzc3OCBcdWM2ZDAgXHVjNTQ4XHVjNWQwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNFx1Yzc4OFx1YjI5NCBcdWM4MTBcdWM3NTggXHVhYzFjXHVjMjE4XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0OTk1IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQ2lyY2xlIGFuZCBQb2ludHMiLCJkZXNjcmlwdGlvbiI6IjxwPllvdSBhcmUgZ2l2ZW4gTiBwb2ludHMgaW4gdGhlIHh5LXBsYW5lLiBZb3UgaGF2ZSBhIGNpcmNsZSBvZiByYWRpdXMgb25lIGFuZCBtb3ZlIGl0IG9uIHRoZSB4eS1wbGFuZSwgc28gYXMgdG8gZW5jbG9zZSBhcyBtYW55IG9mIHRoZSBwb2ludHMgYXMgcG9zc2libGUuIEZpbmQgaG93IG1hbnkgcG9pbnRzIGNhbiBiZSBzaW11bHRhbmVvdXNseSBlbmNsb3NlZCBhdCB0aGUgbWF4aW11bS4gQSBwb2ludCBpcyBjb25zaWRlcmVkIGVuY2xvc2VkIGJ5IGEgY2lyY2xlIHdoZW4gaXQgaXMgaW5zaWRlIG9yIG9uIHRoZSBjaXJjbGUuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvY25wLmdpZlwiIHN0eWxlPVwiaGVpZ2h0OjQ3MnB4OyB3aWR0aDo0OTNweFwiIFwvPjxcL3A+XHJcblxyXG48cD5GaWcgMS4gQ2lyY2xlIGFuZCBQb2ludHM8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBpbnB1dCBjb25zaXN0cyBvZiBhIHNlcmllcyBvZiBkYXRhIHNldHMsIGZvbGxvd2VkIGJ5IGEgc2luZ2xlIGxpbmUgb25seSBjb250YWluaW5nIGEgc2luZ2xlIGNoYXJhY3RlciAmIzM5OzAmIzM5Oywgd2hpY2ggaW5kaWNhdGVzIHRoZSBlbmQgb2YgdGhlIGlucHV0LiBFYWNoIGRhdGEgc2V0IGJlZ2lucyB3aXRoIGEgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgTiwgd2hpY2ggaW5kaWNhdGVzIHRoZSBudW1iZXIgb2YgcG9pbnRzIGluIHRoZSBkYXRhIHNldC4gSXQgaXMgZm9sbG93ZWQgYnkgTiBsaW5lcyBkZXNjcmliaW5nIHRoZSBjb29yZGluYXRlcyBvZiB0aGUgcG9pbnRzLiBFYWNoIG9mIHRoZSBOIGxpbmVzIGhhcyB0d28gZGVjaW1hbCBmcmFjdGlvbnMgWCBhbmQgWSwgZGVzY3JpYmluZyB0aGUgeC0gYW5kIHktY29vcmRpbmF0ZXMgb2YgYSBwb2ludCwgcmVzcGVjdGl2ZWx5LiBUaGV5IGFyZSBnaXZlbiB3aXRoIGZpdmUgZGlnaXRzIGFmdGVyIHRoZSBkZWNpbWFsIHBvaW50LjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGFzc3VtZSAxICZsdDs9IE4gJmx0Oz0gMzAwLCAwLjAgJmx0Oz0gWCAmbHQ7PSAxMC4wLCBhbmQgMC4wICZsdDs9IFkgJmx0Oz0gMTAuMC4gTm8gdHdvIHBvaW50cyBhcmUgY2xvc2VyIHRoYW4gMC4wMDAxLiBObyB0d28gcG9pbnRzIGluIGEgZGF0YSBzZXQgYXJlIGFwcHJveGltYXRlbHkgYXQgYSBkaXN0YW5jZSBvZiAyLjAuIE1vcmUgcHJlY2lzZWx5LCBmb3IgYW55IHR3byBwb2ludHMgaW4gYSBkYXRhIHNldCwgdGhlIGRpc3RhbmNlIGQgYmV0d2VlbiB0aGUgdHdvIG5ldmVyIHNhdGlzZmllcyAxLjk5OTkgJmx0Oz0gZCAmbHQ7PSAyLjAwMDEuIEZpbmFsbHksIG5vIHRocmVlIHBvaW50cyBpbiBhIGRhdGEgc2V0IGFyZSBzaW11bHRhbmVvdXNseSB2ZXJ5IGNsb3NlIHRvIGEgc2luZ2xlIGNpcmNsZSBvZiByYWRpdXMgb25lLiBNb3JlIHByZWNpc2VseSwgbGV0IFAxLCBQMiwgYW5kIFAzIGJlIGFueSB0aHJlZSBwb2ludHMgaW4gYSBkYXRhIHNldCwgYW5kIGQxLCBkMiwgYW5kIGQzIHRoZSBkaXN0YW5jZXMgZnJvbSBhbiBhcmJpdHJhcmlseSBzZWxlY3RlZCBwb2ludCBpbiB0aGUgeHktcGxhbmUgdG8gZWFjaCBvZiB0aGVtIHJlc3BlY3RpdmVseS4gVGhlbiBpdCBuZXZlciBzaW11bHRhbmVvdXNseSBob2xkcyB0aGF0IDAuOTk5OSAmbHQ7PSBkaSAmbHQ7PSAxLjAwMDEgKGkgPSAxLCAyLCAzKS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCBkYXRhIHNldCwgcHJpbnQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBtYXhpbXVtIG51bWJlciBvZiBwb2ludHMgaW4gdGhlIGRhdGEgc2V0IHRoYXQgY2FuIGJlIHNpbXVsdGFuZW91c2x5IGVuY2xvc2VkIGJ5IGEgY2lyY2xlIG9mIHJhZGl1cyBvbmUuIE5vIG90aGVyIGNoYXJhY3RlcnMgaW5jbHVkaW5nIGxlYWRpbmcgYW5kIHRyYWlsaW5nIHNwYWNlcyBzaG91bGQgYmUgcHJpbnRlZC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=