POJ-1981 Circle and Points 单位圆覆盖_weixin_30363817的博客-程序员秘密

技术标签: c/c++  

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

  容易想到直接枚举两个点,然后确定一个圆来枚举,算法复杂度O(n^3).

  这题还有O(n^2*lg n)的算法。将每个点扩展为单位圆,依次枚举每个单位圆,枚举剩下的单位圆,如果有交点,每个圆产生两个交点,然后对产生的2n个交点极角排序,判断被覆盖最多的弧,被覆盖相当于这个弧上的点为圆心的圆可以覆盖到覆盖它的那些点,所以被覆盖最多的弧就是答案了。

O(n^3):

  1 //STATUS:C++_AC_4032MS_208KB
  2 #include <functional>
  3 #include <algorithm>
  4 #include <iostream>
  5 //#include <ext/rope>
  6 #include <fstream>
  7 #include <sstream>
  8 #include <iomanip>
  9 #include <numeric>
 10 #include <cstring>
 11 #include <cassert>
 12 #include <cstdio>
 13 #include <string>
 14 #include <vector>
 15 #include <bitset>
 16 #include <queue>
 17 #include <stack>
 18 #include <cmath>
 19 #include <ctime>
 20 #include <list>
 21 #include <set>
 22 #include <map>
 23 using namespace std;
 24 //using namespace __gnu_cxx;
 25 //define
 26 #define pii pair<int,int>
 27 #define mem(a,b) memset(a,b,sizeof(a))
 28 #define lson l,mid,rt<<1
 29 #define rson mid+1,r,rt<<1|1
 30 #define PI acos(-1.0)
 31 //typedef
 32 typedef long long LL;
 33 typedef unsigned long long ULL;
 34 //const
 35 const int N=310;
 36 const int INF=0x3f3f3f3f;
 37 const int MOD=100000,STA=8000010;
 38 const LL LNF=1LL<<60;
 39 const double EPS=1e-8;
 40 const double OO=1e15;
 41 const int dx[4]={-1,0,1,0};
 42 const int dy[4]={
    0,1,0,-1};
 43 const int day[13]={
    0,31,28,31,30,31,30,31,31,30,31,30,31};
 44 //Daily Use ...
 45 inline int sign(double x){
    return (x>EPS)-(x<-EPS);}
 46 template<class T> T gcd(T a,T b){
    return b?gcd(b,a%b):a;}
 47 template<class T> T lcm(T a,T b){
    return a/gcd(a,b)*b;}
 48 template<class T> inline T lcm(T a,T b,T d){
    return a/d*b;}
 49 template<class T> inline T Min(T a,T b){
    return a<b?a:b;}
 50 template<class T> inline T Max(T a,T b){
    return a>b?a:b;}
 51 template<class T> inline T Min(T a,T b,T c){
    return min(min(a, b),c);}
 52 template<class T> inline T Max(T a,T b,T c){
    return max(max(a, b),c);}
 53 template<class T> inline T Min(T a,T b,T c,T d){
    return min(min(a, b),min(c,d));}
 54 template<class T> inline T Max(T a,T b,T c,T d){
    return max(max(a, b),max(c,d));}
 55 //End
 56 
 57 struct Node{
 58     double x,y;
 59 }nod[N],O;
 60 int n;
 61 
 62 double dist(Node &a,Node &b)
 63 {
 64     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 65 }
 66 
 67 void getO(Node &a,Node &b,int dir)
 68 {
 69     double t=dist(a,b)/2.0;
 70     t=dir*sqrt((1.0-t*t));
 71     if(a.y==b.y){
 72         O.x=(a.x+b.x)/2.0;
 73         O.y=a.y+t;
 74     }
 75     else if(a.x==b.x){
 76         O.y=(a.y+b.y)/2.0;
 77         O.x=a.x+t;
 78     }
 79     else {
 80         double kt;
 81         kt=atan(-(a.x-b.x)/(a.y-b.y));
 82         O.x=(a.x+b.x)/2.0+cos(kt)*t;
 83         O.y=(a.y+b.y)/2.0+sin(kt)*t;
 84     }
 85 }
 86 
 87 int main()
 88 {
 89  //   freopen("in.txt","r",stdin);
 90     int i,j,k,ans,tot;
 91     while(scanf("%d",&n) && n)
 92     {
 93         ans=1;
 94         for(i=0;i<n;i++){
 95             scanf("%lf%lf",&nod[i].x,&nod[i].y);
 96         }
 97         for(i=0;i<n;i++){
 98             for(j=i+1;j<n;j++){
 99                 if(dist(nod[i],nod[j])<2.0){
100                     getO(nod[i],nod[j],1);
101                     for(tot=2,k=0;k<n;k++){
102                         if(k==i || k==j)continue;
103                         if(dist(O,nod[k])-1.0<EPS)tot++;
104                     }
105                     if(tot>ans)ans=tot;
106                 }
107             }
108         }
109 
110         printf("%d\n",ans);
111     }
112     return 0;
113 }    

O(n^2*lg n): 建立极角的时候,不是以枚举的圆心 i->j 方向的向量,而是 j->i 方向的向量,因为 i->j 方向不能完全判断圆的方向,在极角排序的时候会出错。

  1 //STATUS:C++_AC_750MS_212KB
  2 #include <functional>
  3 #include <algorithm>
  4 #include <iostream>
  5 //#include <ext/rope>
  6 #include <fstream>
  7 #include <sstream>
  8 #include <iomanip>
  9 #include <numeric>
 10 #include <cstring>
 11 #include <cassert>
 12 #include <cstdio>
 13 #include <string>
 14 #include <vector>
 15 #include <bitset>
 16 #include <queue>
 17 #include <stack>
 18 #include <cmath>
 19 #include <ctime>
 20 #include <list>
 21 #include <set>
 22 #include <map>
 23 using namespace std;
 24 //using namespace __gnu_cxx;
 25 //define
 26 #define pii pair<int,int>
 27 #define mem(a,b) memset(a,b,sizeof(a))
 28 #define lson l,mid,rt<<1
 29 #define rson mid+1,r,rt<<1|1
 30 #define PI acos(-1.0)
 31 //typedef
 32 typedef long long LL;
 33 typedef unsigned long long ULL;
 34 //const
 35 const int N=310;
 36 const int INF=0x3f3f3f3f;
 37 const int MOD=100000,STA=8000010;
 38 const LL LNF=1LL<<60;
 39 const double EPS=1e-8;
 40 const double OO=1e15;
 41 const int dx[4]={-1,0,1,0};
 42 const int dy[4]={
    0,1,0,-1};
 43 const int day[13]={
    0,31,28,31,30,31,30,31,31,30,31,30,31};
 44 //Daily Use ...
 45 inline int sign(double x){
    return (x>EPS)-(x<-EPS);}
 46 template<class T> T gcd(T a,T b){
    return b?gcd(b,a%b):a;}
 47 template<class T> T lcm(T a,T b){
    return a/gcd(a,b)*b;}
 48 template<class T> inline T lcm(T a,T b,T d){
    return a/d*b;}
 49 template<class T> inline T Min(T a,T b){
    return a<b?a:b;}
 50 template<class T> inline T Max(T a,T b){
    return a>b?a:b;}
 51 template<class T> inline T Min(T a,T b,T c){
    return min(min(a, b),c);}
 52 template<class T> inline T Max(T a,T b,T c){
    return max(max(a, b),c);}
 53 template<class T> inline T Min(T a,T b,T c,T d){
    return min(min(a, b),min(c,d));}
 54 template<class T> inline T Max(T a,T b,T c,T d){
    return max(max(a, b),max(c,d));}
 55 //End
 56 
 57 struct Node{
 58     double x,y;
 59 }nod[N];
 60 struct Point{
 61     double angle;
 62     int id;
 63     bool operator < (const Point& a)const{
 64         return angle!=a.angle?angle<a.angle:id>a.id;
 65     }
 66 }p[N*2];
 67 int n;
 68 
 69 double dist(Node &a,Node &b)
 70 {
 71     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
 72 }
 73 
 74 int slove()
 75 {
 76     int i,j,ans,tot,k,cnt;
 77     ans=1;
 78     for(i=0;i<n;i++){
 79         for(j=k=0;j<n;j++){
 80             if(j==i || dist(nod[i],nod[j])>2.0)continue;
 81             double angle=atan2(nod[i].y-nod[j].y,nod[i].x-nod[j].x);  //注意为i-j的向量方向
 82             double phi=acos(dist(nod[i],nod[j])/2);
 83             p[k].angle=angle-phi;p[k++].id=1;
 84             p[k].angle=angle+phi;p[k++].id=-1;
 85         }
 86         sort(p,p+k);
 87         for(tot=1,j=0;j<k;j++){
 88             tot+=p[j].id;
 89             ans=Max(ans,tot);
 90         }
 91     }
 92     return ans;
 93 }
 94 
 95 int main()
 96 {
 97  //   freopen("in.txt","r",stdin);
 98     int i;
 99     while(~scanf("%d",&n) && n)
100     {
101         for(i=0;i<n;i++)
102             scanf("%lf%lf",&nod[i].x,&nod[i].y);
103 
104         printf("%d\n",slove());
105     }
106     return 0;
107 }

 

转载于:https://www.cnblogs.com/zhsl/p/3192144.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30363817/article/details/96049177

智能推荐

Tomcat DBCP 连接池泄露_org.apache.tomcat.dbcp.pool2.impl.throwablecallsta_duobstek的博客-程序员秘密

连接池泄露是指:应用一直持有数据库连接未释放,数据源一般都会配置maxActive属性以限制数据源使用的数据库连接的峰值,此时,当应用持有的连接数超过maxActive的值之后,将会报错,并使得服务器无法再响应需要访问数据库的请求:1org.apache.tomcat.dbcp.dbcp.SQLNestedException: Cannot get a

gitlab上fork的项目如何获取源更新_weixin_30839881的博客-程序员秘密

1、添加上游项目地址git remote add upstream URL2、查看远程仓库信息可以看到上游项目地址已经添加进来了git remote -v3、获取上游项目更新获取到的更新会被保存在本地的upstream/master分支git fetch upstream4、合并到本地分支如果不是master分支,要切换到 mas...

恒虚警算法及其MATLAB实现_罗东琦的博客-程序员秘密

简单介绍了恒虚警算法的原理,并给出相应的MATLAB代码。

【LeetCode】34. 在排序数组中查找元素的第一个和最后一个位置(JAVA)_rabbitsockx的博客-程序员秘密

原题地址:https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/submissions/题目描述:给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。你的算法时间复杂度必须是 O(log n) 级别。...

【Python】轻量级分布式任务调度系统-RQ_cojm55771的博客-程序员秘密

一 前言 Redis Queue 一款轻量级的P分布式异步任务队列,基于Redis作为broker,将任务存到redis里面,然后在后台执行指定的Job。就目前而言有三套成熟的工具celery,huey ,rq 。...

”单元测试“理解与感悟_weixin_33908217的博客-程序员秘密

百度:单元测试(unittesting),是在计算机编程中,针对程序模块(软件设计的最小单位)来进行正确性检验的测试工作。程序单元是应用的最小可测试部件。对于单元测试中单元的含义,一般来说,要根据实际情况去判定其具体含义,如C语言中单元指一个函数,Java里单元指一个类,图形化的软件中可以指一个窗口或一个菜单等。总的来说,单元就是人为规定的最小的被测功能模块。单元测试是在软件开发过程中要进行的最低...

随便推点

ipc(一)_"zcm::zcm zcm {\"ipc\"};"_hnzmdzcm的博客-程序员秘密

一、Linux下进程间通信方式总结(管道篇)IPC全称interprocess communication,即进程间通信。在shell下可以输入命令ipcs来查看。[[email protected] ipc]$ ipcs -a------ Shared Memory Segments --------key        shmid      owner      perm

Elasticsearch-安装与配置_elasticsearch config elasticsearch.yml xms_XiangYida的博客-程序员秘密

1.下载与安装第一步很重要,这里就是入坑的开始了,到底该安装哪个版本。最新的是7.0最好不要选最新的,选个接近最新的吧。版本问题后面整合的时候再讨论。下载之前最好先去官网看看文档简单学习一下Elasticsearch吧。入门部分几分钟就能看完。1.1 下载1.1.1 先进elasticsearch的官网,点击右上角download,然后选择elasticsearch进入下载页面。点...

cocostudio与cocosbuilder对比整理_Ruby丫丫的博客-程序员秘密

cocostudio与cocosbuilder对比整理   1.cocosbuilder1个编辑器就实现了除骨骼系统(完整的骨骼系统)以外的ui、动画、场景编辑器几乎所有功能 2.studio编辑器按照不同功能分出3个,看似更清晰了,但是当做一个动画+ui控件界面时还必须用到场景编辑。比如同1 界面你想实现2层ui之间显示一个动画效果,你得做2个ui文件+1

idea使用docker插件dockerfile-maven-plugin无法连接远程服务器报错: Connection timed out: connect_看见什么的博客-程序员秘密

将远程服务地址配置到系统变量,重启电脑 ;,(注意:远程服务上docker 要开启远程访问)

用python做双人五子棋_使用python实现简单五子棋游戏_python五子棋人机不用模块_我们要发财了的博客-程序员秘密

用python实现五子棋简单人机模式的练习过程,供大家参考,具体内容如下第一次写博客,我尽力把它写好。最近在初学python,今天就用自己的一些粗浅理解,来记录一下这几天的python简单人机五子棋游戏的练习,下面是实现过程的理解(是在cmd中运行的):主要流程: 重点内容首先是模块及类的划分棋子类和棋盘类的方法对策略类里的功能进行细分,调用棋子类和棋盘类写出判断输赢的方法用main函数进行整个游戏进度的控制模块及类的划分类的划分涉及到了面向对象的内容,根据五子棋

SSD基础知识一_ssd psid_chipfish的博客-程序员秘密

1、SSD分为俩大类,一是基于闪存,特点是可以移动,适应性强,适合个人用户,但是寿命短。二是基于DRAM,特点是性能高,但是需要独立的电源供电。2、内部构成:主要部分是:NAND Flash负责存储,主控芯片负责读取,写入。3、Flash闪存的体系结构:       page:读写的最小单元       Block:由page组成,是最小的擦除单位       Plane: