POJ 2079 Triangle（凸包，最大三角形）

POJ 2079 Triangle（凸包，最大三角形）

​​接下来是求解最大的面积。简单的做法是直接来个n^3枚举，这应该会超时。再一次利用凸多边形的凸性，旋转卡壳。 寻找最大的三角形，先是两个点不动，接着点3个点不断在凸包上跑动，到最大三角形的位置时，更新最大面积。三个顶点均这样更新，多边形变回原来的形状时，变化一个点，另外两个点都会因此受到影响，这样持续下去，完成一个大循环。

#include #include #include #include using namespace std;const int N=5e4+10;struct point{ int x,y;}p[N];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 dis2(point p1,point p2){ return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);}int cmp1(point p1,point p2){ return p1.x0;}int top;point sta[N];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 ans=0; //转一圈就能找完 sta[top]=sta[0]; int i=0,j=1,k=2; while(k!=0){ int ii=i,jj=j,kk=k,temp; while((temp=cross(sta[i],sta[j],sta[k]))=top) k=0; } ans=max(ans,temp); while((temp=cross(sta[i],sta[j],sta[k]))=top) j=0; } ans=max(ans,temp); while((temp=cross(sta[i],sta[j],sta[k]))=top) i=0; } ans=max(ans,temp); if(i==ii&&j==jj&&k==kk) k=(k+1)%top; //回到原来的形状，k+1,k==0时跳出 } return ans;}int main(){ //freopen("cin.txt","r",stdin); int n; while(cin>>n&&(n!=-1)){ for(int i=0;i

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