【计算几何】 POJ 1981 Circle and Points

求最多有多少个点落在 一个单位圆内

复杂度 O ( n^2 log n)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <string>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <math.h>
using namespace std;
#include <queue>
#include <stack>
#include <vector>
#include <deque>
#include <set>
#include <map>
#define cler(arr, val)    memset(arr, val, sizeof(arr))
#define IN     freopen ("in.txt" , "r" , stdin);
#define OUT  freopen ("out.txt" , "w" , stdout);
typedef long long  LL;
const int MAXN = 66666;//点数的最大值
const int MAXM = 20006;//边数的最大值
const int INF = 1101521204;
const int mod = 10000007;
const double eps = 0.0000001;
struct point
{
    double x, y;
};
double dis(point p1, point p2)//没开根号
{
    point p3;
    p3.x = p2.x - p1.x;
    p3.y = p2.y - p1.y;
    return p3.x * p3.x + p3.y * p3.y;
}
point find_centre(point p1, point p2)
{
    point p3, mid, centre;
    double b, c, ang;
    p3.x = p2.x - p1.x;
    p3.y = p2.y - p1.y;
    mid.x = (p1.x + p2.x) / 2;
    mid.y = (p1.y + p2.y) / 2;
    b = dis(p1, mid);
    c = sqrt(1 - b);
    if(fabs(p3.y) < eps)//垂线的斜角90度
    {
        centre.x = mid.x;
        centre.y = mid.y + c;
    }
    else
    {
        ang = atan(-p3.x / p3.y);
        centre.x = mid.x + c * cos(ang);
        centre.y = mid.y + c * sin(ang);
    }
    return centre;
}
int main()
{
    int n, ans, tmpans, i, j, k;
    point p[305], centre;
    double tmp;
    while(scanf("%d", &n) && n)
    {
        for(i = 0; i < n; i++)
            scanf("%lf%lf", &p[i].x, &p[i].y);
        ans = 1;
        for(i = 0; i < n; i++)
            for(j = i + 1; j < n; j++)
            {
                if(dis(p[i], p[j]) > 4) continue;
                tmpans = 0;
                centre = find_centre(p[i], p[j]);
                for(k = 0; k < n; k++)
                {
                    tmp = dis(centre, p[k]);
                    if(tmp <= 1.000001) tmpans++;
                }
                if(ans < tmpans) ans = tmpans;
            }
        printf("%d\n", ans);
    }
    return 0;
}