微网站建设流程,做网站湘潭,wordpress 分类 文章列表,一般做一个网站多少钱/*这是用的有旋转卡壳的思想。
首先确定i#xff0c;j#xff0c;对k进行循环#xff0c;知道找到第一个k使得cross(i,j,k)cross(i,j,k1),如果ki进入下一次循环。
对j#xff0c;k进行旋转#xff0c;每次循环之前更新最大值#xff0c;然后固定一个j#xff0c;同样… /*这是用的有旋转卡壳的思想。
首先确定ij对k进行循环知道找到第一个k使得cross(i,j,k)cross(i,j,k1),如果ki进入下一次循环。
对jk进行旋转每次循环之前更新最大值然后固定一个j同样找到一个k使得cross(i,j,k)cross(i,j,k1)。对j进行操作继续进行下一次
知道jk为止。
*/ #include iostream
#include cstdio
#include algorithm
#include cmathusing namespace std;struct point{double x,y;
}p[1000100];
int n;int ans[1000100],st[1000100],cnt,stop;bool cmp(point A, point B){if(A.yB.y) return true;else if(A.yB.y){if(A.xB.x) return true;}return false;
}double multi(point a,point b,point c){point p1; p1.xa.x-c.x; p1.ya.y-c.y;point p2; p2.xb.x-c.x; p2.yb.y-c.y;return p1.x*p2.y-p1.y*p2.x;
}void slove(){cntstop0;st[stop]0; st[stop]1;for(int i2;in;i){while(stop1multi(p[i],p[st[stop-1]],p[st[stop-2]])0) stop--;st[stop]i;}for(int i0;istop;i)ans[cnt]st[i];stop0; st[stop]n-1; st[stop]n-2;for(int in-3;i0;i--){while(stop1multi(p[i],p[st[stop-1]],p[st[stop-2]])0) stop--;st[stop]i;}for(int i1;istop-1;i)ans[cnt]st[i];
/* for(int i0;icnt;i)coutans[i]endl;coutendl;*/
}double Triangle(point a,point b,point c){point p1; p1.xa.x-c.x; p1.ya.y-c.y;point p2; p2.xb.x-c.x; p2.yb.y-c.y;return fabs((p1.x*p2.y-p1.y*p2.x)*1.0)/2.0;
}double Area(){int q; int j;double anst0;for(int i0;icnt;i){j(i1)%cnt;q(j1)%cnt;while(Triangle(p[ans[i]],p[ans[j]],p[ans[q]])Triangle(p[ans[i]],p[ans[j]],p[ans[(q1)%cnt]])q!i)q(q1)%cnt; //枚举了当前最远的K点 anstmax(anst,Triangle(p[ans[i]],p[ans[j]],p[ans[q]]));if(qi) continue;while(j!iq!i){anstmax(anst,Triangle(p[ans[i]],p[ans[j]],p[ans[q]]));while(Triangle(p[ans[i]],p[ans[j]],p[ans[q]])Triangle(p[ans[i]],p[ans[j]],p[ans[(q1)%cnt]])q!i)q(q1)%cnt;j(j1)%cnt;}}return anst;
}int main(){while(scanf(%d,n)!EOF){// if(n-1) break;for(int i0;in;i){scanf(%lf%lf,p[i].x,p[i].y);}sort(p,pn,cmp);slove();double anst0;anstmax(anst,Area());printf(%.2lf\n,anst);}return 0;
}转载于:https://www.cnblogs.com/jie-dcai/p/3891337.html
