Circle and Points#299

Circle and Points

2 seconds
64 megabytes
Medium

You are given points in the -plane and a circle of radius .

Find the maximum number of points that can simultaneously be inside or on the boundary of a circle of radius . A point is considered within the circle if it is inside or exactly on the circle's boundary.

Input

The input consists of several data sets. The end of input is indicated by a line containing a single .

Each data set starts with a line containing a single integer (1 \le N \le 300), the number of points.

Next follow lines, each containing two decimal numbers and (0.0 \le X, Y \le 10.0), the coordinates of a point. Coordinates are given with digits after the decimal point.

No two points are closer than to each other. No two points within a data set are at approximately distance from each other, that is, the distance between any pair of points never satisfies 1.9999 \le d \le 2.0001.

Furthermore, no three points within a data set are simultaneously very close to being co-circular with a unit circle. Specifically, for any three distinct points P_1, P_2, P_3 in a data set, and for any arbitrary point in the plane, let d_1, d_2, d_3 be the distances from that point to P_1, P_2, and P_3, respectively. Then it never simultaneously holds that 0.9999 \le d_i \le 1.0001 for i = 1,2,3.

Output

For each data set, print the maximum number of points that can simultaneously be inside or on a unit circle, one per line.

Examples

Example 1

Loading
Loading