215
POJ 1873 凸包+枚舉
題意：一片森林，每棵樹有坐標，做成柵欄的長度，本身價值，讓求砍下任意棵樹做成柵欄將剩下的樹圍上，要求被砍的這些樹價值和最小，價值相同時要求被砍下的樹最少，輸出被砍的樹，和做完柵欄後剩餘的長度。
這題就用位運算枚舉，最高的複雜度不過2的15次方。1的狀態表示被砍的，0的狀態表示剩下的。需要注意的是凸包求的是三個點以上的，那麼0個點，1個點，2個點的情況需要特判。
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
PointType x,y;
};
struct tree
{
point coor;
double val,length;
};
point data[105],stack[105],MinA;
int top;
tree tdata[20];
PointType Direction(point pi,point pj,point pk) //判斷向量PiPj在向量PiPk的順逆時針方向 +順-逆0共線
{
return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
PointType k=Direction(MinA,a,b);
if(k>0) return 1;
if(k<0) return 0;
return Dis(MinA,a)>Dis(MinA,b);
}
void Graham_Scan(point *a,int numa)
{
if(numa==0||numa==1)
{
top=0;
return;
}
if(numa==2)
{
top=2;
stack[0]=data[0],stack[1]=data[1];
return;
}
for(int i=0; i<numa; i++)
if(a[i].y<a[0].y||(a[i].y==a[0].y&&a[i].x<a[0].x))
swap(a[i],a[0]);
MinA=a[0],top=0;
sort(a+1,a+numa,cmp);
stack[top++]=a[0],stack[top++]=a[1],stack[top++]=a[2];
for(int i=3; i<numa; i++)
{
while(Direction(stack[top-2],stack[top-1],a[i])<0)
top--;
stack[top++]=a[i];
}
}
int main()
{
int n,numans,ans,s=0;
double sumval,anslen;
while(~scanf("%d",&n),n)
{
sumval=1e9;
for(int i=0; i<n; i++)
scanf("%lf%lf%lf%lf",&tdata[i].coor.x,&tdata[i].coor.y,&tdata[i].val,&tdata[i].length);
for(int i=1; i<(1<<n)-1; i++)
{
int k=i,nownum=0;
double nowsum=0,sumlen=0,nowval=0;
for(int j=0; j<n; j++)
{
if(k&1)
sumlen+=tdata[j].length,nowval+=tdata[j].val;
else
data[nownum++]=tdata[j].coor;
k>>=1;
}
Graham_Scan(data,nownum);
for(int q=0; q<top; q++)
nowsum+=Dis(stack[q],stack[(q+1)%top]);
if(sumlen>=nowsum&&(nowval<sumval||(nowval==sumval&&n-nownum<numans)))
ans=i,numans=n-nownum,sumval=nowval,anslen=sumlen-nowsum;
}
if(s)
printf("\n");
printf("Forest %d\n",++s),printf("Cut these trees:");
for(int i=0; i<n; i++)
{
if(ans&1)
printf(" %d",i+1);
ans>>=1;
}
printf("\nExtra wood: %.2f\n",anslen);
}
return 0;
}
最後更新：2017-04-03 20:43:08