|
|
Posted on 2010-05-05 21:04 Uriel 閱讀(578) 評論(2) 編輯 收藏 引用 所屬分類: POJ 、 計算幾何
慚愧，這題從中午寫到晚上，一開始一直卡著調也調不了，搞到晚上沒辦法換了個凸包模板，然后歷經各種NC錯誤終于AC。。 浙大模板凸包那里應該沒什么問題，用過多少次了，應該是自己寫掛了吧。。- - 題意是有n棵樹，每棵的坐標，價值和長度已知，要砍掉若干根，用他們圍住其他樹，問損失價值最小的情況下又要長度足夠圍住其他樹，砍掉哪些樹。。 Discuss稱這題為Final的水題。。于是我也水過去了。。枚舉+構造凸包判可行。。代碼如下。。凸包那里可以無視。。- -直接貼模板的。。
  /**//*
 Problem: 1873 User: Uriel
Memory: 192K Time: 454MS
Language: C++ Result: Accepted
 */
 #include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
struct point
 {
int flag;
double x,y,v,l;
};
point P[100],convex[100],p1[100],p2[100],p[100];
double resl,suml,sumv,minv,ans;
int n,ansn;
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));
}
bool cmp(point a,point b)
{
return a.flag < b.flag;
}
int partition(point a[],int p,int r)
{
int i=p,j=r+1,k;
double ang,dis;
point R,S;
k=(p+r)/2;
R=a[p];a[p]=a[k];a[k]=R;R=a[p];
dis=Dis(R,a[0]);
while(1)
  {
while(1)
{
++i;
if(i>r)
{
i=r;
break;
 }
ang=multiply(R,a[i],a[0]);
if(ang>0)
break;
else if(ang==0)
{
if(Dis(a[i],a[0])>dis)
break;
}
}
while(1)
{
--j;
if(j<p)
{
j=p;
break;
}
ang=multiply(R,a[j],a[0]);
if(ang<0)
break;
else if(ang==0)
{
if(Dis(a[j],a[0])<dis)
break;
}
}
if(i>=j)break;
S=a[i];
a[i]=a[j];
a[j]=S;
}
a[p]=a[j];
a[j]=R;
return j;
}
void anglesort(point a[],int p,int r)
{
if(p<r)
{
int q=partition(a,p,r);
anglesort(a,p,q-1);
anglesort(a,q+1,r);
}
}
/**//*PointSet傳入散點,凸包上的點存在ch,n為點數，len為凸包頂點數*/
void Graham_scan(point PointSet[],point ch[],int n,int &len)
{
int i,k=0,top=2;
point tmp;
for(i=1;i<n;i++)
if ( PointSet[i].x<PointSet[k].x ||
(PointSet[i].x==PointSet[k].x) && (PointSet[i].y<PointSet[k].y))
k=i;
tmp=PointSet[0];
PointSet[0]=PointSet[k];
PointSet[k]=tmp;
anglesort(PointSet,1,n-1);
if(n<3)
{
len=n;
for(int i=0;i<n;i++) ch[i]=PointSet[i];
return ;
}
ch[0]=PointSet[0];
ch[1]=PointSet[1];
ch[2]=PointSet[2];
for (i=3;i<n;i++)
{
while (multiply(PointSet[i],ch[top],ch[top-1])>=0) top--;
ch[++top]=PointSet[i];
}
len=top+1;
}
int main()
{
int cse,g=1,i,j,k1,M,k2;
while(scanf("%d",&n),n)
{
for(i=0;i<n;i++)
{
scanf("%lf %lf %lf %lf",&P[i].x,&P[i].y,&P[i].v,&P[i].l);
P[i].flag=i+1;
}
minv=1e20;
for(i=0;i<(1<<n);i++)
{
k1=0;k2=0;
sumv=0;suml=0;
for(j=0;j<n;j++)
{
if(!(i & (1<<j)))
{
p1[k1].x=P[j].x;
p1[k1].y=P[j].y;
k1++;
}
else
{
p2[k2].flag=P[j].flag;
sumv+=P[j].v;
suml+=P[j].l;
k2++;
}
}
Graham_scan(p1,convex,k1,M);
resl=0;
for(int j=0;j<M-1;j++)
{
resl+=Dis(convex[j],convex[j+1]);
}
resl+=Dis(convex[0],convex[M-1]);
if(resl<=suml && sumv<minv)
{
ans=suml-resl;
minv=sumv;
ansn=k2;
for(j=0;j<k2;j++)p[j].flag=p2[j].flag;
}
}
printf("Forest %d\n",g++);
printf("Cut these trees:");
for(i=0;i<ansn;i++)if(p[i].flag!=p[i-1].flag)printf(" %d",p[i].flag);
printf("\n");
printf("Extra wood: %.2lf\n\n",ans);
}
// system("PAUSE");
return 0;
}
Feedback
# re: POJ 1873 The Fortified Forest---凸包+枚舉 回復 更多評論
2012-03-20 20:24 by
5
1 1 2 2
2 2 3 3
3 3 4 4
4 4 5 5
5 5 6 6
崩潰數據
# re: POJ 1873 The Fortified Forest---凸包+枚舉 回復 更多評論
2012-03-20 21:02 by
@debuger
謝謝提醒，原來沒有考慮共線的情況，有共線時凸包那里會有bug
似乎改成這樣就可以
while (multiply(PointSet[i], ch[top], ch[top - 1]) >= 0 && top >= 1) top--;
還有問題的話歡迎指教～
|