栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 1981 Circle and Points

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 1981 Circle and Points

#include <stdio.h>#include <iostream>#include <cmath>#include <algorithm>#define PI acos(-1.0)using namespace std;const int N=305;int n;struct Point{double x,y;}p[N];struct Angle{double ang;bool is;}angle[N*2];int cmp(Angle M,Angle N){    return M.ang<N.ang;}double dist(Point a,Point b){    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}double k(Point a,Point b){    double ki=atan(fabs((b.y-a.y)/(b.x-a.x)));    if(b.y-a.y>0){        if(b.x-a.x<0)        ki=PI-ki;    }    else{        if(b.x<a.x) ki+=PI;        else ki=2*PI-ki;    }    return ki;}void solve(){    int res=1,top;    double dis,now,tmp;    for(int i=0;i<n;i++){        top=0;        for(int j=0;j<n;j++){ if(i==j) continue; dis=dist(p[i],p[j]); if(dis>2.0) continue; now=k(p[i],p[j]); tmp=acos(dis/2.0); angle[top].ang=now-tmp; angle[top++].is=1; angle[top].ang=now+tmp; angle[top++].is=0;        }        if(top<res) continue;        sort(angle,angle+top,cmp);        int count=1;        for(int j=0;j<top;j++){ if(angle[j].is) count++; else count--; res=max(res,count);        }    }    printf("%dn",res);}int main(){    while(scanf("%d",&n)!=EOF&&n){        for(int i=0;i<n;i++){ scanf("%lf%lf",&p[i].x,&p[i].y);        }        solve();    }}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/380075.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号