POJ 2187 Beauty Contest（凸包优化 || 凸包+旋转卡壳）

POJ 2187 Beauty Contest（凸包优化 || 凸包+旋转卡壳）

​​http://poj.org/problem?id=2187​​

大意：求解点和点之间的最大距离的平方。

记得曾经有一道CF的题自己写了一个3重循环也过了，当时自己怀疑计算机一秒是运算10^9吗，还是数据太弱。。。写了一个1e9的程序，果断超时。看来1e8才是保险值 TLE：

#include #include using namespace std;const int N=5e4+10;struct point{ int x,y;}p[N];int dis(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int main(){ int n; while(cin>>n){ int ans=0; for(int i=0;itemp?ans:temp; } } printf("%d\n",ans); } return 0;}

后经分析，此题需要用凸包优化：

我又画个图说明：

我们总能在凸包上寻找另一个点使得凸包上一对点的距离大于图中灰色线段的长。换句话说，题目中要求的距离（的平方）就在凸包上。 （time: 157ms  memory: 632k          嘿嘿，效果还行）

#include #include #include using namespace std;const int N=5e4+10;struct point{ int x,y;}p[N];int dis(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int cross(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int cmp1(point p1,point p2){ return p1.x0;}point ans[N];int top;void convex(int n){ top=0; sort(p,p+n,cmp1); sort(p+1,p+n,cmp2); ans[top++]=p[0]; ans[top++]=p[1]; for(int i=2;i0) ans[top++]=p[i]; else { top--; while(top>=2&&cross(ans[top-2],ans[top-1],p[i])<=0) top--; ans[top++]=p[i]; } } //ans[top++]=p[0]; //因为本题比较距离的特殊性，所以不用围成凸包}int main(){ //freopen("cin.txt","r",stdin); int n; while(cin>>n){ for(int i=0;itemp?res:temp; } } printf("%d\n",res); } return 0;}

后来听说，这题涉及到旋转卡壳和

最远点对。啊，原来还有其他做法。先到这里，继续学习。。。

========================================================================

2016.01.23

学习了旋转卡壳，现在用旋转卡壳来做它：

旋转卡壳用于凸包已经求得基础上寻找一对点的最大距离（当然他还有其他作用）。

凸多边形直径定理：凸多边形P的直径等于P的所有平行支撑线之间距离的最大值。

旋转卡壳的算法展示图片：

（我打不开上面这个链接。。。）

这篇博文的算法实现是比较好的： ​​rotating(){ int q=1,ans=0; sta[top]=sta[0]; for(int i=0;icross(sta[i],sta[i+1],sta[q])) q=(q+1)%top; ans=max(ans,max(dis(sta[i],sta[q]),dis(sta[i+1],sta[q+1]))); // ans=max(ans,max(dis(sta[i],sta[q]),dis(sta[i+1],sta[q]))); } return ans;}

ans=max(ans,max(dis(sta[i],sta[q]),dis(sta[i+1],sta[q+1]))); 的解释： 主要考虑到平行线的情况。

POJ 2187 居然用下面那条注释的语句也过了，这应该是数据弱了。。

#include #include #include using namespace std;const int N=5e4+10;struct point{ int x,y;}p[N];int dis(point a,point b){ return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);}int cross(point p0,point p1,point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int cmp1(point p1,point p2){ return p1.x0;}point sta[N];int top;void convex(int n){ top=0; sort(p,p+n,cmp1); sort(p+1,p+n,cmp2); sta[top++]=p[0]; sta[top++]=p[1]; for(int i=2;i0) sta[top++]=p[i]; else { top--; while(top>=2&&cross(sta[top-2],sta[top-1],p[i])<=0) top--; sta[top++]=p[i]; } }}int rotating(){ int q=1,ans=0; sta[top]=sta[0]; for(int i=0;icross(sta[i],sta[i+1],sta[q])) q=(q+1)%top; ans=max(ans,max(dis(sta[i],sta[q]),dis(sta[i+1],sta[q+1]))); } return ans;}int main(){ //freopen("cin.txt","r",stdin); int n; while(cin>>n){ for(int i=0;i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。