【题目链接】 http://poj.org/problem?id=1981

【题目大意】

  给出平面上一些点,问一个半径为1的圆最多可以覆盖几个点

【题解】

  我们对于每个点画半径为1的圆,那么在两圆交弧上的点所画的圆,一定可以覆盖这两个点
  我们对于每个点计算出其和其它点的交弧,对这些交弧计算起末位置对于圆心的极角,
  对这些我们进行扫描线操作,统计最大交集数量就是答案。

【代码】

#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
using namespace std;
double EPS=1e-10;
double add(double a,double b){
if(abs(a+b)<EPS*(abs(a)+abs(b)))return 0;
return a+b;
}
const int MAX_N=310;
struct P{
double x,y;
P(){}
P(double x,double y):x(x),y(y){}
P operator + (P p){return P(add(x,p.x),add(y,p.y));}
P operator - (P p){return P(add(x,-p.x),add(y,-p.y));}
P operator * (double d){return P(x*d,y*d);}
double dot(P p){return add(x*p.x,y*p.y);} //点积
double det(P p){return add(x*p.y,-y*p.x);} //叉积
}ps[MAX_N];
double dist(P p,P q){return sqrt((p-q).dot(p-q));}
struct PolarAngle{
double angle;
bool flag;
}as[MAX_N];
bool cmp_a(PolarAngle a,PolarAngle b){
return a.angle<b.angle;
}
int solve(int n,double r){
int ans=1;
for(int i=0;i<n;i++){
int m=0; double d;
for(int j=0;j<n;j++){
if(i!=j&&(d=dist(ps[i],ps[j]))<=2*r){
double phi=acos(d/2);
double theta=atan2(ps[j].y-ps[i].y,ps[j].x-ps[i].x);
as[m].angle=theta-phi,as[m++].flag=1;
as[m].angle=theta+phi,as[m++].flag=0;
}
}sort(as,as+m,cmp_a);
for(int sum=1,j=0;j<m;j++){
if(as[j].flag)sum++;
else sum--;
ans=max(ans,sum);
}
}return ans;
}
int N;
int main(){
while(scanf("%d",&N),N){
for(int i=0;i<N;i++)scanf("%lf%lf",&ps[i].x,&ps[i].y);
printf("%d\n",solve(N,1.0));
}return 0;
}

最新文章

  1. EF连接PostgreSql
  2. win32记事本程序(一)
  3. VS2010编译Qt4.8.2的64版本库
  4. 【转】HTML - embed 与 object 之争
  5. 【leetcode】13. Roman to Integer
  6. Android之记账本
  7. 【推荐】推荐一本学习ExtJS4的好书《ExtJS江湖》(含pdf电子书和源代码下载地址)
  8. springboot用thymeleaf模板的paginate分页
  9. Java-this
  10. Sql Server 数据类型与 C# 数据类型对照
  11. dev-client.js-配合dev-server.js监听html文件改动也能够触发自动刷新
  12. 【ibatis】IBatis的动态SQL的写法
  13. docker容器资源配额控制
  14. (转)Ubuntu12.04上NFS Server安装使用过程
  15. mui.back()返回刷新功能
  16. 专业软件 —— Adobe Audition
  17. MySQL的WHERE语句中BETWEEN与IN的用法和他们的区别
  18. C++string类常用函数
  19. 还是要精简开发呀,VS2015太大,VS2010不想装
  20. DJI SDK iOS 开发之中的一个:前言

热门文章

  1. BZOJ2097: [Usaco2010 Dec]Exercise 奶牛健美操 贪心+伪树dp+二分
  2. CentOS 7, 升级python到3.x
  3. POJ2502:Subway(最短路)
  4. BZOJ1051:受欢迎的牛(并查集 / Tarjan)
  5. ng4转义html
  6. vue2学习篇一 $mount()手动挂载
  7. PhoneGap之自定义插件
  8. jquery序列化表单
  9. PCIe 中的Capability 结构的寻址
  10. bzoj4839 [Neerc2016]Abbreviation