首页 > 其他 > 详细

Circle and Points

时间:2019-07-29 12:37:30      阅读:74      评论:0      收藏:0      [点我收藏+]

技术分享图片

技术分享图片

技术分享图片

 

#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;

struct Point
{
    double x,y;
    Point() {};
    Point(int _x,int _y):x(_x),y(_y) {};
} p[400];

double dis(Point a,Point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}

struct node
{
    double angle;
    bool in;
} a[180000];
int n,cnt;

bool cmp(node a,node b)
{
    return a.angle!=b.angle?a.angle<b.angle:a.in>b.in;
}

void MaxCircleCover()
{
    int ans=1;
    for (int i=1; i<=n; i++)
    {
        int cnt=0;
        for (int j=1; j<=n; j++)
        {
            if (i==j||dis(p[i],p[j])>2.0)
            {
                continue;
            }
            double angle=atan2(p[i].y-p[j].y,p[i].x-p[j].x);
            double phi=acos(dis(p[i],p[j])/2);
            a[cnt].angle=angle-phi;
            a[cnt++].in=1;
            a[cnt].angle=angle+phi;
            a[cnt++].in=0;
        }
        sort(a,a+cnt,cmp);
        int tmp=1;
        for (int i=0; i<cnt; i++)
        {
            if (a[i].in)
            {
                tmp++;
            }
            else
            {
                tmp--;
            }
            ans=max(ans,tmp);
        }
    }
    printf("%d\n",ans);
}

int main()
{
    while (scanf("%d",&n),n)
    {
        for (int i=1; i<=n; i++)
        {
            scanf("%lf%lf",&p[i].x,&p[i].y);
        }
        MaxCircleCover();
    }
    return 0;
}

  

Circle and Points

原文:https://www.cnblogs.com/Accpted/p/11263029.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!