POJ 1981 Circle and Points (扫描线)
2024-08-20 12:43:53
【题目链接】 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;
}
最新文章
- EF连接PostgreSql
- win32记事本程序(一)
- VS2010编译Qt4.8.2的64版本库
- 【转】HTML - embed 与 object 之争
- 【leetcode】13. Roman to Integer
- Android之记账本
- 【推荐】推荐一本学习ExtJS4的好书《ExtJS江湖》(含pdf电子书和源代码下载地址)
- springboot用thymeleaf模板的paginate分页
- Java-this
- Sql Server 数据类型与 C# 数据类型对照
- dev-client.js-配合dev-server.js监听html文件改动也能够触发自动刷新
- 【ibatis】IBatis的动态SQL的写法
- docker容器资源配额控制
- (转)Ubuntu12.04上NFS Server安装使用过程
- mui.back()返回刷新功能
- 专业软件 —— Adobe Audition
- MySQL的WHERE语句中BETWEEN与IN的用法和他们的区别
- C++string类常用函数
- 还是要精简开发呀,VS2015太大,VS2010不想装
- DJI SDK iOS 开发之中的一个:前言
热门文章
- BZOJ2097: [Usaco2010 Dec]Exercise 奶牛健美操 贪心+伪树dp+二分
- CentOS 7, 升级python到3.x
- POJ2502:Subway(最短路)
- BZOJ1051:受欢迎的牛(并查集 / Tarjan)
- ng4转义html
- vue2学习篇一 $mount()手动挂载
- PhoneGap之自定义插件
- jquery序列化表单
- PCIe 中的Capability 结构的寻址
- bzoj4839 [Neerc2016]Abbreviation