Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
WA了无数次才发现,三角形边可以不是凸包上的边~~Orz啊~~~~/* 题意:平面上给出n个点,然后其中任意三个点能组成三角形,求出最大的三角形面积 先求一次凸包,然后在凸包上枚举三角形的第一个顶点i,把其他两个顶点拿来旋转(旋转卡壳模板)。 此题要考虑到三角形的边可以不是凸包上的边 */ #include<iostream> #include<queue> #include<cstdio> #include<algorithm> #include<cstring> #include<iomanip> #include<map> #include<cstdlib> #include<cmath> #include<vector> #define LL long long #define IT __int64 #define zero(x) fabs(x)<eps #define mm(a,b) memset(a,b,sizeof(a)) const int INF=0x7fffffff; const double inf=1e8; const double eps=1e-10; const double PI=acos(-1.0); const int Max=100000; using namespace std; int sign(double x) { return (x>eps)-(x<-eps); } typedef struct Node { double x; double y; Node(const double &_x=0, const double &_y=0) : x(_x), y(_y) {} void input() { scanf("%lf%lf",&x,&y); } void output() { printf("%lf %lf\n",x,y); } } point; point list[Max],stack[Max]; int n; int top; int cnt; int curcnt; double xmult(point p0,point p1,point p2) { return(p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); } double dmult(point p0,point p1,point p2) { return(p1.x-p0.x)*(p2.x-p0.x)+(p1.y-p0.y)*(p2.y-p0.y); } double Distance(point p1,point p2)// 返回两点之间欧氏距离 { return( sqrt( (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y) ) ); } bool cmp(point p1,point p2) { double temp; temp=xmult(list[0],p1,p2); if(temp>0) return true; if(temp==0&&(Distance(list[0],p1)<Distance(list[0],p2))) return true; return false; } void convex_hull()//凸包模板 { int i; for(i=1; i<n; i++) { point temp; if((list[i].y<list[0].y)||(list[i].y==list[0].y&&list[i].x<list[0].x)) swap(list[0],list[i]); } sort(list+1,list+n,cmp); top=1; stack[0]=list[0]; stack[1]=list[1]; for(i=2; i<n; i++) { while(top>=1&&xmult(stack[top-1],stack[top],list[i])<=0) top--; top++; stack[top]=list[i]; } } double rotating_calipers()//旋转卡壳 { int i,j=1,k=2; double ans=0; stack[++top]=stack[0]; for(i=0; i<top; i++) { //cout<<fabs(xmult(stack[p],stack[p+1],stack[q]))<<" "<<fabs(xmult(stack[p],stack[p+1],stack[q+1]))<<endl; //while(xmult(stack[p],stack[p+1],stack[q+1])>xmult(stack[p],stack[p+1],stack[q])) //q=(q+1)%top; //ans=max(ans,max(fabs(xmult(stack[p],stack[p+1],stack[q])),fabs(xmult(stack[p],stack[p+1],stack[q+1])))); //cout<<ans<<endl; /*开始没考虑边上的两点可以不是凸包上的点,WA无数次顿时发觉*/ while(fabs(xmult(stack[(k+1)%n],stack[i],stack[j]))>fabs(xmult(stack[k],stack[i],stack[j]))) k=(k+1)%n; while(fabs(xmult(stack[k],stack[i],stack[(j+1)%n]))>fabs(xmult(stack[k],stack[i],stack[j]))) j=(j+1)%n; ans=max(ans,fabs(xmult(stack[k],stack[i],stack[j]))); } return ans; } int main() { int m,i,j; double area; while(cin>>n&&n>=0) { for(i=0;i<n;i++) { list[i].input(); } convex_hull(); //cout<<top<<endl; area=rotating_calipers(); printf("%.2lf\n",area/2); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator