题意：
给出一系列点，这些点之间的距离都在2附近，求一个单位圆最多能包含几个点。
要点：
极限情况就是2个点在圆的边上，这样就可以求出圆心，再枚举看其他点在不在圆内即可，复杂度是n^3。
#include#include #include #include #include #define eps 1e-8using namespace std;struct node{ double x, y;}p[310];double dis(node a, node b){ return sqrt((a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y));}void get_center(node a, node b, node& center)//已知两点和半径求圆心{ node mid; mid.x = (a.x + b.x) / 2.0; mid.y = (a.y + b.y) / 2.0; double angle = atan2(a.x - b.x, b.y - a.y);//注意这里 double d = sqrt(1 - dis(mid, a)*dis(mid, a)); center.x = mid.x + d*cos(angle); center.y = mid.y + d*sin(angle); //printf("%lf %lf\n", center.x, center.y);}int main(){ int n, i, j, k; while (scanf("%d", &n), n) { for (i = 1; i <= n; i++) scanf("%lf%lf", &p[i].x,&p[i].y); int ans = 1; for(i=1;i<=n;i++) for (j = i + 1; j <= n; j++) { if (dis(p[i], p[j]) > 2.0) continue; node center; get_center(p[i], p[j],center); int cnt = 0; for (k = 1; k <= n; k++) { if (dis(center, p[k]) < 1.0 + eps) cnt++; } ans = max(cnt, ans); } printf("%d\n", ans); } return 0;}