我们可以知道，当这个单位圆可以覆盖到最多的点的时候，必定最少有两个点位于这个圆的圆周上，于是就有网上众多的O(N^3)的枚举两个在圆上的点的暴搜做法。
然而这题是可以用圆交来做的。
我们以一条鱼的位置作为圆心，半径为1的圆的周围随便找一个点都能把这条鱼抓到。这时，我们可以做出很多个这样的圆，半径都为1。
然后，求一下这些圆的交集，叠起来的最高层数就是最多能获得的鱼的数目。
这里的圆交不需要实现求面积这部分，于是只需要离散一下交点就行了。
1y。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <iomanip>
#include <cmath> using namespace std; const double EPS = 1e-;
const double PI = acos(-1.0);
inline int sgn(double x) { return (x > EPS) - (x < -EPS);}
template<class T> T sqr(T x) { return x * x;}
typedef pair<double, double> Point;
#define x first
#define y second Point operator + (Point a, Point b) { return Point(a.x + b.x, a.y + b.y);}
Point operator - (Point a, Point b) { return Point(a.x - b.x, a.y - b.y);}
Point operator * (Point a, double p) { return Point(a.x * p, a.y * p);}
Point operator * (double p, Point a) { return Point(a.x * p, a.y * p);}
Point operator / (Point a, double p) { return Point(a.x / p, a.y / p);} inline double cross(Point a, Point b) { return a.x * b.y - a.y * b.x;}
inline double dot(Point a, Point b) { return a.x * b.x + a.y * b.y;}
inline double veclen(Point a) { return sqrt(dot(a, a));}
inline double angle(Point a) { return atan2(a.y, a.x);}
inline Point vecunit(Point a) { return a / veclen(a);}
inline Point normal(Point a) { return Point(-a.y, a.x) / veclen(a);} struct Line {
Point s, t;
Line() {}
Line(Point s, Point t) : s(s), t(t) {}
Point vec() { return t - s;}
Point point(double p) { return s + vec() * p;}
} ;
inline Point llint(Line a, Line b) { return a.point(cross(b.vec(), a.s - b.s) / cross(a.vec(), b.vec()));} struct Circle {
Point c;
double r;
Circle() {}
Circle(Point c, double r) : c(c), r(r) {}
Point point(double p) { return c + r * Point(cos(p), sin(p));}
bool in(Point p) { return sgn(veclen(p - c) - r) < ;}
} ; const double R = 1000.0;
const int N = ;
int n;
Circle cir[N]; void input() {
cin >> n;
for (int i = ; i < n; i++) {
cin >> cir[i].c.x >> cir[i].c.y;
cir[i].c = cir[i].c * R;
cir[i].r = R;
}
} bool ccint(int _a, int _b, double *sol) {
Circle a = cir[_a], b = cir[_b];
double d = veclen(a.c - b.c), dr = fabs(a.r - b.r);
if (sgn(d - a.r - b.r) > ) return ;
if (sgn(dr - d) >= ) {
if (a.r < b.r || sgn(a.r - b.r) == && _a < _b) {
sol[] = -PI;
sol[] = PI;
return ;
}
return ;
}
double ang = angle(b.c - a.c);
double da = acos(fabs(sqr(a.r) + sqr(d) - sqr(b.r)) / ( * a.r * d));
sol[] = ang - da;
sol[] = ang + da;
return ;
} typedef pair<double, int> Event;
Event ev[N << ];
bool cmp(Event a, Event b) {
if (sgn(a.x - b.x)) return a.x < b.x;
return a.y > b.y;
} int cal(int id) {
int tt = ;
double _[];
for (int i = ; i < n; i++) {
if (i == id) continue;
if (ccint(id, i, _)) {
if (_[] < -PI) {
ev[tt++] = Event(_[] + * PI, );
ev[tt++] = Event(PI, -);
ev[tt++] = Event(-PI, );
ev[tt++] = Event(_[], -);
} else if (_[] > PI) {
ev[tt++] = Event(_[], );
ev[tt++] = Event(PI, -);
ev[tt++] = Event(-PI, );
ev[tt++] = Event(_[] - * PI, -);
} else {
ev[tt++] = Event(_[], );
ev[tt++] = Event(_[], -);
}
}
}
int cnt = , mx = ;
sort(ev, ev + tt, cmp);
for (int i = ; i < tt; i++) {
cnt += ev[i].y;
mx = max(mx, cnt);
}
return mx;
} int work() {
int mx = ;
for (int i = ; i < n; i++) mx = max(mx, cal(i));
return mx;
} int main() {
//freopen("in", "r", stdin);
ios::sync_with_stdio();
cout << setiosflags(ios::fixed) << setprecision();
int _;
cin >> _;
while (_--) {
input();
cout << work() << endl;
}
return ;
}
——written by Lyon