題目大意：在二維平面中給出 n 個(gè)點(diǎn)，再給出一個(gè)固定大小的圓，問(wèn)如何放置這個(gè)圓可以使其覆蓋最多的點(diǎn)

題目分析：首先不難想到一種 n^3 的做法，就是兩層循環(huán)去枚舉兩個(gè)點(diǎn)，因?yàn)閮蓚€(gè)不同的點(diǎn)就可以確定下來(lái)兩個(gè)圓了（對(duì)稱(chēng)的），然后對(duì)于這 2 * n * n 個(gè)圓的每一個(gè)來(lái)說(shuō)，再用一層循環(huán)去枚舉 n 個(gè)點(diǎn)，計(jì)算一下有多少個(gè)點(diǎn)可以被覆蓋到就可以了

考慮優(yōu)化，假如分別以點(diǎn) i 和點(diǎn) j 為圓心，以 r 為半徑做出兩個(gè)相交的圓，比較顯然的是，如果在相交的陰影部分中任選一點(diǎn)作為圓心，同樣以 r 作為半徑做圓，那么點(diǎn) i 和點(diǎn) j 都可以同時(shí)被覆蓋到，如下圖所示：

所以我們不妨映射到其中一個(gè)圓的弧上，稱(chēng)這一段為相交弧，這樣一來(lái)此題就得以?xún)?yōu)化了：

先用一層循環(huán)去固定點(diǎn) i 作為圓心，然后枚舉點(diǎn) j 同樣也作為圓心，兩個(gè)圓若能相交的話(huà)求出相交弧，最多有 n 段相交弧，對(duì)于以點(diǎn) i 為圓心的圓周來(lái)說(shuō)，其中某個(gè)點(diǎn)被覆蓋的次數(shù)，就是以該點(diǎn)為圓心所能覆蓋的點(diǎn)數(shù)，所以求出被覆蓋最多的位置即可

如何去求這個(gè)位置呢？利用差分的思想，對(duì) n 段相交弧，也就是 2 * n 個(gè)交點(diǎn)進(jìn)行極角排序，然后掃一遍求最大連續(xù)子段和就是答案了，時(shí)間復(fù)雜度為 n^2logn

很讓人煩心的一點(diǎn)是，這個(gè)題目用 atan2 的極角排序很輕松 AC，但用叉積排序總是多多少少會(huì)出現(xiàn)一些不可描述的問(wèn)題，一直卡在 97 分的位置，糾結(jié)三天了，沒(méi)精力再耗下去了。。就這樣隨緣吧

代碼：

n^3

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110; // `計(jì)算幾何模板` const double eps = 1e-8; const double pi = acos(-1.0); const int maxp = 1010; //`Compares a double to zero` int sgn(double x){if(fabs(x) < eps)return 0;if(x < 0)return -1;else return 1; } struct Point{double x,y;Point(){}Point(double _x,double _y){x = _x;y = _y;}void input(){scanf("%lf%lf",&x,&y);}void output(){printf("%.2f %.2f\n",x,y);}bool operator == (Point b)const{return sgn(x-b.x) == 0 && sgn(y-b.y) == 0;}bool operator < (Point b)const{return sgn(x-b.x)== 0?sgn(y-b.y)<0:x<b.x;}Point operator -(const Point &b)const{return Point(x-b.x,y-b.y);}//叉積double operator ^(const Point &b)const{return x*b.y - y*b.x;}//點(diǎn)積double operator *(const Point &b)const{return x*b.x + y*b.y;}//返回長(zhǎng)度double len(){return hypot(x,y);//庫(kù)函數(shù)}//返回兩點(diǎn)的距離double distance(Point p){return hypot(x-p.x,y-p.y);}Point operator +(const Point &b)const{return Point(x+b.x,y+b.y);}//`化為長(zhǎng)度為r的向量`Point trunc(double r){double l = len();if(!sgn(l))return *this;r /= l;return Point(x*r,y*r);}//`逆時(shí)針旋轉(zhuǎn)90度`Point rotleft(){return Point(-y,x);}//`順時(shí)針旋轉(zhuǎn)90度`Point rotright(){return Point(y,-x);} }point[N]; //圓 struct circle{Point p;//圓心double r;//半徑circle(){}circle(Point _p,double _r){p = _p;r = _r;}circle(double x,double y,double _r){p = Point(x,y);r = _r;}//輸入void input(){p.input();scanf("%lf",&r);}//輸出void output(){printf("%.2lf %.2lf %.2lf\n",p.x,p.y,r);}bool operator == (circle v){return (p==v.p) && sgn(r-v.r)==0;}bool operator < (circle v)const{return ((p<v.p)||((p==v.p)&&sgn(r-v.r)<0));}//`點(diǎn)和圓的關(guān)系`//`0 圓外`//`1 圓上`//`2 圓內(nèi)`int relation(Point b){double dst = b.distance(p);if(sgn(dst-r) < 0)return 2;else if(sgn(dst-r)==0)return 1;return 0;}//`兩圓的關(guān)系`//`5 相離`//`4 外切`//`3 相交`//`2 內(nèi)切`//`1 內(nèi)含`//`需要Point的distance`//`測(cè)試：UVA12304`int relationcircle(circle v){double d = p.distance(v.p);if(sgn(d-r-v.r) > 0)return 5;if(sgn(d-r-v.r) == 0)return 4;double l = fabs(r-v.r);if(sgn(d-r-v.r)<0 && sgn(d-l)>0)return 3;if(sgn(d-l)==0)return 2;if(sgn(d-l)<0)return 1;}//`求兩個(gè)圓的交點(diǎn)，返回0表示沒(méi)有交點(diǎn)，返回1是一個(gè)交點(diǎn)，2是兩個(gè)交點(diǎn)`//`需要relationcircle`//`測(cè)試：UVA12304`int pointcrosscircle(circle v,Point &p1,Point &p2){int rel = relationcircle(v);if(rel == 1 || rel == 5)return 0;double d = p.distance(v.p);double l = (d*d+r*r-v.r*v.r)/(2*d);double h = sqrt(r*r-l*l);Point tmp = p + (v.p-p).trunc(l);p1 = tmp + ((v.p-p).rotleft().trunc(h));p2 = tmp + ((v.p-p).rotright().trunc(h));if(rel == 2 || rel == 4)return 1;return 2;}//`得到過(guò)a,b兩點(diǎn)，半徑為r1的兩個(gè)圓`static int gercircle(Point a,Point b,double r1,circle &c1,circle &c2){circle x(a,r1),y(b,r1);int t = x.pointcrosscircle(y,c1.p,c2.p);if(!t)return 0;c1.r = c2.r = r1;return t;} };int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);double r;scanf("%lf",&r);int n;scanf("%d",&n);for(int i=1;i<=n;i++)point[i].input();int ans=1;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){circle c1,c2;circle::gercircle(point[i],point[j],r,c1,c2);int sum1=0,sum2=0;for(int k=1;k<=n;k++){if(c1.relation(point[k]))sum1++;if(c2.relation(point[k]))sum2++;}ans=max(ans,sum1);ans=max(ans,sum2);}printf("%d\n",ans);return 0; }

n^2logn

//#pragma GCC optimize(2) //#pragma GCC optimize("Ofast","inline","-ffast-math") //#pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=110;const double eps=1e-8;int sgn(double x) {if(fabs(x)<=eps)return 0;if(x<0)return -1;return 1; }struct Point {double x,y;void input(){scanf("%lf%lf",&x,&y);}double distance(const Point& t)const{return hypot(x-t.x,y-t.y);} }point[N];struct Node {double alpha;int flag;Node(double alpha,int flag):alpha(alpha),flag(flag){}bool friend operator<(const Node& a,const Node& b){if(sgn(a.alpha-b.alpha)==0)return a.flag>b.flag;return sgn(a.alpha-b.alpha)<0;} };int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);double r;scanf("%lf",&r);int n;scanf("%d",&n);for(int i=1;i<=n;i++) point[i].input();int ans=1;for(int i=1;i<=n;i++){vector<Node>node;for(int j=1;j<=n;j++){if(i==j)continue;double dis=point[i].distance(point[j]);if(sgn(dis-2*r)>0)continue;double alpha=atan2(point[j].y-point[i].y,point[j].x-point[i].x);double phi=acos(dis/(2.0*r));node.push_back(Node(alpha-phi,1));node.push_back(Node(alpha+phi,-1));}sort(node.begin(),node.end());int sum=0;for(auto it:node){sum+=it.flag;ans=max(ans,sum+1);}}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的中石油训练赛 - Gone Fishing(固定大小的圆可以覆盖最多的点)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。