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

poj1981-单位圆最多覆盖点

程序员文章站 2022-04-01 10:44:12
...

计算几何题。昨天的比赛题,这类题数据不会特别大,只要能推出公式,就能解。

比赛时,只顾着找模版,没有认真去分析题。期间想到过解题思路,由于不自信,没有去实现!!!!poj1981-单位圆最多覆盖点

解题思路:

根据最远两点确定圆心,判断圆内最多的点数。不断修改圆心,记录最大的点数。遍历一遍就是答案。

趁着这几天总结一下学过的一点计算几何,加油!!!。

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
const double inf=1e-6;
struct Point{
    double x,y;
};
double Distance(Point a,Point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
Point get_center(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 = Distance(p1, mid);
    c = sqrt(2.5*2.5 - b);
    if(fabs(p3.y) < inf)//垂线的斜角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;
}

Point p[305];
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        for(i=0;i<n;i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        int ans=1;
	//枚举所有点。从i-n的点
         for(int i=0;i<n;i++)
        {
            for(int j=i+1;j<n;j++)//搜过的不必再搜
            {

                if(Distance(p[i],p[j])-25>inf) continue;//距离大于直径长度
                int tpans=0;
                Point center=get_center(p[i],p[j]);
                for(int k=0;k<n;k++)
                    if(sqrt(Distance(p[k],center))-2.5<inf) ++tpans;
                if(tpans>ans) ans=tpans;
            }
        }
        printf("%d\n",ans);
    }

}