|
|
Posted on 2009-09-20 00:48 Uriel 閱讀(829) 評(píng)論(0) 編輯 收藏 引用 所屬分類: POJ 、 計(jì)算幾何
求凸包上的點(diǎn)構(gòu)成的三角形最大面積。。
開始抄模板構(gòu)造凸包然后O(n^3)...聽說有人優(yōu)化就過了。。但是自己無論怎么優(yōu)化都TLE。。無奈去強(qiáng)大的旋轉(zhuǎn)卡殼。。抄了那段之后終于過了。。旋轉(zhuǎn)卡殼還有些不懂，也基本不會(huì)應(yīng)用。。要好好看下
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;
//計(jì)算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算法順時(shí)針構(gòu)造包含所有共線點(diǎn)的凸包,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--);
}
//構(gòu)造凸包接口函數(shù),傳入原始點(diǎn)集大小n,點(diǎn)集p(p原有順序被打亂!)
//返回凸包大小,凸包的點(diǎn)在convex中
//參數(shù)maxsize為1包含共線點(diǎn),為0不包含共線點(diǎn),缺省為1
//參數(shù)clockwise為1順時(shí)針構(gòu)造,為0逆時(shí)針構(gòu)造,缺省為1
//在輸入僅有若干共線點(diǎn)時(shí)算法不穩(wěn)定,可能有此類情況請(qǐng)另行處理!
//不能去掉點(diǎn)集中重合的點(diǎn)
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;
}
強(qiáng)大的旋轉(zhuǎn)卡殼。。。
/**//*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));
}
//計(jì)算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算法順時(shí)針構(gòu)造包含所有共線點(diǎn)的凸包,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--);
}
//構(gòu)造凸包接口函數(shù),傳入原始點(diǎn)集大小n,點(diǎn)集p(p原有順序被打亂!)
//返回凸包大小,凸包的點(diǎn)在convex中
//參數(shù)maxsize為1包含共線點(diǎn),為0不包含共線點(diǎn),缺省為1
//參數(shù)clockwise為1順時(shí)針構(gòu)造,為0逆時(shí)針構(gòu)造,缺省為1
//在輸入僅有若干共線點(diǎn)時(shí)算法不穩(wěn)定,可能有此類情況請(qǐng)另行處理!
//不能去掉點(diǎn)集中重合的點(diǎn)
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;
}
|