欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【计算几何】 POJ 1981 Circle and Points

程序员文章站 2022-03-02 10:41:18
...

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

复杂度 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;
}