题目链接

题意 : 给你很多点和一个半径r,这个半径为r的圆能覆盖的最多的点是多少。

思路 : 对每个点做半径为 r 的圆, 求交集,交集最多的区域的被覆盖次数就是能覆盖的最多的点。贴两个链接,分析的挺好代码写得挺好

 #include <stdio.h>
#include <string.h>
#include <math.h>
#include <iostream>
#include <algorithm> using namespace std ; const double eps = 1e- ;
const double PI = acos(-1.0) ;
int n ;
double r ; struct point
{
double x,y ;
}p[] ;
struct node
{
double angle ;
int flag ;
}q[] ; inline int dcmp(double d)
{
return d < -eps ? - : d > eps ;
}
bool cmp(const node &a,const node &b)//角度区间排序
{
if(dcmp(a.angle-b.angle) == ) return a.flag > b.flag ;
return a.angle < b.angle ;
}
double Sqrt(double x)
{
return x*x ;
}
double dist(const point &a,const point &b)
{
return sqrt(Sqrt(a.x-b.x)+Sqrt(a.y-b.y)) ;
} int main()
{
while(~scanf("%d %lf",&n,&r))
{
if(n == ) break ;
for(int i = ; i < n ; i++)
scanf("%lf %lf",&p[i].x,&p[i].y) ;
int ans = ;
for(int i = ; i < n ; i++)
{
int m = ;
for(int j = ; j < n ; j++)
{
if(i == j) continue ;
double d = dist(p[i],p[j]) ;
if(d > *r+0.001) continue ;
double s = atan2(p[j].y-p[i].y,p[j].x-p[i].x) ;
if(s < ) s += *PI ;//角度区间修正
double ph = acos(d/2.0/r) ;//圆心角转区间
q[m++].angle = s - ph + *PI ;q[m-].flag = ;
q[m++].angle = s + ph + *PI ;q[m-].flag = - ;
}
sort(q,q+m,cmp) ;
int sum = ;
for(int j = ; j < m ; j++)
ans = max(ans,sum += q[j].flag) ;
}
printf("It is possible to cover %d points.\n",ans+) ;
}
return ;
}

最新文章

  1. Verilog HDL那些事_建模篇笔记(实验七:数码管电路驱动)
  2. 修改 页面中默认的select样式
  3. UvaLive6661 Equal Sum Sets dfs或dp
  4. GNU for x86汇编语法
  5. Ubuntu安装gfortran
  6. jqGrid中选择的行的数据[转]
  7. angular-ui-bootstrap插件API - Pager
  8. 如何迭代输出某文件夹下的所有文件的路径?(os.walk用法)
  9. JS for循环 if判断、white循环。小练习
  10. JDK动态代理给Spring事务埋下的坑!
  11. C# Note26: [MethodImpl(MethodImplOptions.Synchronized)]与lock机制
  12. 【ORIGINATE】详解
  13. 爬虫----beautifulsoup的简单使用
  14. 简述JavaScript作用域与作用域链
  15. for-each、for-in和for-of的区别
  16. Python 静态方法
  17. 初识Spring Webflux
  18. 20155227 2016-2017-2 《Java程序设计》第十周学习总结
  19. Spring.Net框架三:使用Spring.Net框架实现多数据库
  20. CCF 字符串匹配(find()函数的使用)

热门文章

  1. Cocos2d-x数据持久化-查询数据
  2. Oracle创建新用户
  3. (poj 3177) Redundant Paths
  4. 用一天的时间学习Java EE中的SSH框架
  5. 压力测试 tpcc-mysql
  6. Mysql数据库迁移 Ubuntu14.04
  7. SQL 存储过程加事务的使用
  8. js定义参数默认值
  9. 【CLR VIA C#】读书笔记
  10. OS/400相关介绍