#P1981. Circle and Points

Circle and Points

描述

你被给予 NN 个位于 xyxy-平面上的点。你有一个半径为 11 的圆,并且可以在xy xy-平面上移动这个圆,目的是尽可能多地包围这些点。你需要找出在最多能同时包围多少个点时的情况。如果一个点位于圆的内部或圆上,则认为该点被圆包围

图示说明1

输入

输入包含一系列数据集,后面是一行只包含一个字符 0'0',表示输入的结束。每个数据集以一行包含一个整数 N 开头,表示数据集中的点的数量。接下来是 N 行描述点的坐标。每一行有两个小数 X 和 Y,分别描述一个点的 x 坐标和 y 坐标。它们的小数点后有五位数字。 你可以假设 1<=N<=3000.0<=X<=10.01 <= N <= 300,0.0 <= X <= 10.0,以及 0.0<=Y<=10.00.0 <= Y <= 10.0。没有两个点的距离小于 0.00010.0001。数据集中没有两个点的距离大约为 2.0。更准确地说,对于数据集中的任何两个点,它们之间的距离 d 永远不满足 1.9999<=d<=2.00011.9999 <= d <= 2.0001。最后,数据集中的没有三个点同时非常接近半径为 1 的圆。更准确地说,设 P1P2P1、P2 P3P3 是数据集中的任意三个点,d1d2d1、d2d3d3 是从坐标平面中的一个任意选定点到它们各自的距离。那么,永远不会同时满足 0.9999<=di<=1.0001(i=1,2,3)0.9999 <= di <= 1.0001 (i = 1, 2, 3)。

输出

对于每个数据集,输出一行,包含一个整数,表示该数据集中能够被一个半径为 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

来源

日本2004年国内赛