Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 2079 Triangle---计算几何

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!=&& 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!=&& 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!=&& 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!=&& 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;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理