|
|
Posted on 2010-05-05 21:04 Uriel 阅读(549) 评论(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--;
还有问题的话欢迎指教～
|