시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
1 초 | 128 MB | 145 | 56 | 38 | 38.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인 원 안에 포함되어있는 점의 개수를 출력한다.
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
2 5 5 11
ICPC > Regionals > Asia Pacific > Japan > Japan Domestic Contest > 2004 Japan Domestic Contest D번