|
Posted on 2009-09-20 00:48 Uriel 阅读(816) 评论(0) 编辑 收藏 引用 所属分类: POJ 、 计算几何
求凸包上的点构成的三角形最大面积。。 开始抄模板构造凸包然后O(n^3)...听说有人优化就过了。。但是自己无论怎么优化都TLE。。无奈去强大的旋转卡壳。。抄了那段之后终于过了。。旋转卡壳还有些不懂,也基本不会应用。。要好好看下 TLE到死的代码。。
/**//*Problem: 2079 User: Gilhirith Memory: N/A Time: N/A Language: C++ Result: Time Limit Exceeded*/
#include<math.h> #include<stdio.h> #include<stdlib.h>
#define MAXN 50010 #define eps 1e-8 #define zero(x) (((x)>0?(x):-(x))<eps)
struct point{double x,y;};
point P[MAXN],convex[MAXN]; double prej,prek,maxk,MAX,tmax;
//计算cross product (P1-P0)x(P2-P0) double xmult(point p1,point p2,point p0) { return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }
double Dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }
//graham算法顺时针构造包含所有共线点的凸包,O(nlogn) point p1,p2; int graham_cp(const void* a,const void* b) { double ret=xmult(*((point*)a),*((point*)b),p1); return zero(ret)?(xmult(*((point*)a),*((point*)b),p2)>0?1:-1):(ret>0?1:-1); } void _graham(int n,point* p,int& s,point* ch) { int i,k=0; for (p1=p2=p[0],i=1;i<n;p2.x+=p[i].x,p2.y+=p[i].y,i++) if (p1.y-p[i].y>eps||(zero(p1.y-p[i].y)&&p1.x>p[i].x)) p1=p[k=i]; p2.x/=n,p2.y/=n; p[k]=p[0],p[0]=p1; qsort(p+1,n-1,sizeof(point),graham_cp); for (ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i<n;ch[s++]=p[i++]) for (;s>2&&xmult(ch[s-2],p[i],ch[s-1])<-eps;s--); }
//构造凸包接口函数,传入原始点集大小n,点集p(p原有顺序被打乱!) //返回凸包大小,凸包的点在convex中 //参数maxsize为1包含共线点,为0不包含共线点,缺省为1 //参数clockwise为1顺时针构造,为0逆时针构造,缺省为1 //在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理! //不能去掉点集中重合的点 int graham(int n,point* p,point* convex,int maxsize=1,int dir=1) { point* temp=new point[n]; int s,i; _graham(n,p,s,temp); for (convex[0]=temp[0],n=1,i=(dir?1:(s-1));dir?(i<s):i;i+=(dir?1:-1)) if (maxsize||!zero(xmult(temp[i-1],temp[i],temp[(i+1)%s]))) convex[n++]=temp[i]; delete []temp; return n; }
double Area(int a,int b,int c) { double A,B,C,t,S; A=Dis(convex[a],convex[b]); B=Dis(convex[a],convex[c]); C=Dis(convex[b],convex[c]); t=(A+B+C)/2; S=sqrt(t*(t-A)*(t-B)*(t-C)); // printf("*%.2lf*",S); return S; }
double max(double a,double b) { return a-b>=0?a:b; }
int main() { int N,i,j,k; while(1) { scanf("%d",&N); if(N==-1)break; for(int i=0;i<N;i++) { scanf("%lf %lf",&P[i].x,&P[i].y); } int M=graham(N,P,convex,1,1); MAX=0.0; for(i=0;i<M;i++) { j=(i+1)%M; k=(j+1)%M; while(k!=i && Area(i,j,k)<Area(i,j,(k+1)%M)) { // printf("*%.2f*\n",Area(i,j,k)); k=(k+1)%M; } if(k==i)continue; int kk=(k+1)%M; while(j!=kk && k!=i) { MAX=max(MAX,Area(i,j,k)); while(k!=i && Area(i,j,k)<Area(i,j,(k+1)%M)) { k=(k+1)%M; } j=(j+1)%M; } } printf("%.2lf\n",MAX); } // system("PAUSE"); return 0; }
强大的旋转卡壳。。。
/**//*Problem: 2079 User: Uriel Memory: 1456K Time: 2407MS Language: G++ Result: Accepted*/
#include<math.h> #include<stdio.h> #include<stdlib.h> #define eps 1e-8 #define zero(x) (((x)>0?(x):-(x))<eps)
#define MAXN 50001
struct point{ double x,y; };
point P[MAXN],convex[MAXN]; double MAX; int len;
double Dis(point a,point b) { return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)); }
double multiply(const point& sp,const point& ep,const point& op) { return((sp.x-op.x)*(ep.y-op.y)-(ep.x-op.x)*(sp.y-op.y)); }
//计算cross product (P1-P0)x(P2-P0) double xmult(point p1,point p2,point p0){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y); }
//graham算法顺时针构造包含所有共线点的凸包,O(nlogn) point p1,p2; int graham_cp(const void* a,const void* b){ double ret=xmult(*((point*)a),*((point*)b),p1); return zero(ret)?(xmult(*((point*)a),*((point*)b),p2)>0?1:-1):(ret>0?1:-1); } void _graham(int n,point* p,int& s,point* ch){ int i,k=0; for (p1=p2=p[0],i=1;i<n;p2.x+=p[i].x,p2.y+=p[i].y,i++) if (p1.y-p[i].y>eps||(zero(p1.y-p[i].y)&&p1.x>p[i].x)) p1=p[k=i]; p2.x/=n,p2.y/=n; p[k]=p[0],p[0]=p1; qsort(p+1,n-1,sizeof(point),graham_cp); for (ch[0]=p[0],ch[1]=p[1],ch[2]=p[2],s=i=3;i<n;ch[s++]=p[i++]) for (;s>2&&xmult(ch[s-2],p[i],ch[s-1])<-eps;s--); }
//构造凸包接口函数,传入原始点集大小n,点集p(p原有顺序被打乱!) //返回凸包大小,凸包的点在convex中 //参数maxsize为1包含共线点,为0不包含共线点,缺省为1 //参数clockwise为1顺时针构造,为0逆时针构造,缺省为1 //在输入仅有若干共线点时算法不稳定,可能有此类情况请另行处理! //不能去掉点集中重合的点 int graham(int n,point* p,point* convex,int maxsize=1,int dir=1){ point* temp=new point[n]; int s,i; _graham(n,p,s,temp); for (convex[0]=temp[0],n=1,i=(dir?1:(s-1));dir?(i<s):i;i+=(dir?1:-1)) if (maxsize||!zero(xmult(temp[i-1],temp[i],temp[(i+1)%s]))) convex[n++]=temp[i]; delete []temp; return n; }
double Area(int a,int b,int c) { double A,B,C,t,S; A=Dis(convex[a],convex[b]); B=Dis(convex[a],convex[c]); C=Dis(convex[b],convex[c]); t=(A+B+C)/2; S=sqrt(t*(t-A)*(t-B)*(t-C)); // printf("*%.2lf*",S); return S;
}
double max(double a,double b) { return (a-b)>0?a:b; }
int main() { int N,i,j,k; while(1) { scanf("%d",&N); if(N==-1)break; for(i=0;i<N;i++) { scanf("%lf %lf",&P[i].x,&P[i].y); } int len=graham(N,P,convex,1,1); // for(i=0;i<len;i++) // { // printf("*%.2f %.2f*\n",convex[i].x,convex[i].y); // } MAX=0.0; for(i=0;i<len;i++) { j=(i+1)%len; k=(j+1)%len; // printf("*%.2f*\n",Area(i,j,k)); while(k!=i && Area(i,j,k)<Area(i,j,(k+1)%len)) { k=(k+1)%len; } if(k==i)continue; int kk=(k+1)%len; while(j!=kk && k!=i) { MAX=max(MAX,Area(i,j,k)); while(k!=i && Area(i,j,k)<Area(i,j,(k+1)%len)) { k=(k+1)%len; } j=(j+1)%len; } } printf("%.2f\n",MAX); } // system("PAUSE"); return 0; }
|