2013
11-27

# Catching Fish

Ignatius likes catching fish very much. He has a fishnet whose shape is a circle of radius one. Now he is about to use his fishnet to catch fish. All the fish are in the lake, and we assume all the fish will not move when Ignatius catching them. Now Ignatius wants to know how many fish he can catch by using his fishnet once. We assume that the fish can be regard as a point. So now the problem is how many points can be enclosed by a circle of radius one.Note: If a fish is just on the border of the fishnet, it is also caught by Ignatius.

The input contains several test cases. The first line of the input is a single integer T which is the number of test cases. T test cases follow.
Each test case starts with a positive integer N(1<=N<=300) which indicate the number of fish in the lake. Then N lines follow. Each line contains two floating-point number X and Y (0.0<=X,Y<=10.0). You may assume no two fish will at the same point, and no two fish are closer than 0.0001, no two fish in a test case are approximately at a distance of 2.0. In other words, if the distance between the fish and the centre of the fishnet is smaller 1.0001, we say the fish is also caught.

For each test case, you should output the maximum number of fish Ignatius can catch by using his fishnet once.

4
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

2
5
5
11

/*
* hdu1077/win.cpp
* Created on: 2012-10-25
* Author    : ben
*/
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#include <stack>
#include <string>
#include <vector>
#include <deque>
#include <list>
#include <functional>
#include <numeric>
#include <cctype>
using namespace std;
const int MAXN = 310;
const double eps = 1e-4;
typedef struct MyPoint {
double x, y;
MyPoint() {        x = y = 0;    }
MyPoint(double xx, double yy) {        x = xx;        y = yy;    }
MyPoint(const MyPoint &p1, const MyPoint &p2) {
x = (p1.x + p2.x) / 2;
y = (p1.y + p2.y) / 2;
}
}MyPoint;
inline double mydistance(const MyPoint &p1, const MyPoint &p2) {
return sqrt((p1.x - p2.x) * (p1.x - p2.x) + (p1.y - p2.y) * (p1.y - p2.y));
}
inline MyPoint operator-(const MyPoint &p1, const MyPoint &p2) {
return MyPoint(p1.x - p2.x, p1.y - p2.y);
}
MyPoint points[MAXN];
int N, ans;

inline void getcenter(const MyPoint &p1, const MyPoint &p2, MyPoint &c) {
MyPoint diff = p1 - p2;
MyPoint mid(p1, p2);
double angle;
double high = mydistance(p1, p2) / 2;
high = sqrt(1 - high * high);
if (fabs(diff.x) < eps) {
c.x = mid.x + high;
c.y = mid.y;
} else {
angle = atan(diff.y / diff.x);
c.x = mid.x - high * sin(angle);
c.y = mid.y + high * cos(angle);
}
}

inline bool myjudge(const MyPoint &p1, const MyPoint &p2) {
double dis = mydistance(p1, p2);
return dis <= 1 + eps;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("data.in" , "r", stdin);
#endif
int T;
scanf("%d", &T);
while(T--) {
scanf("%d", &N);
for(int i = 0; i < N; i++) {
scanf("%lf%lf", &points[i].x, &points[i].y);
}
ans = 1;
MyPoint p;
for(int i = 0; i < N; i++) {
for(int j = i + 1; j < N; j++) {
if(mydistance(points[i], points[j]) > 2 + eps + eps) {
continue;
}
getcenter(points[i], points[j], p);
int t = 0;
for(int k = 0; k < N; k++) {
if(myjudge(p, points[k])) {
t++;
}
}
if(t > ans) {
ans = t;
}
}
}
printf("%d\n", ans);
}
return 0;
}

1. [email protected]

2. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。