居然是WF的水题~
二进制枚举砍哪些树，剩余的树围成一个凸包。
因为传数组WA了两发，忘记修改排序数组中的p[0];
#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<stdlib.h>
#include<vector>
#include<cmath>
#include<queue>
#include<set>
using namespace std;
#define N 20
#define LL long long
#define INF 0xfffffff
const double eps = 1e-;
const double pi = acos(-1.0);
const double inf = ~0u>>;
struct point
{
int x,y;
int vi,li;
point(int x=,int y=):x(x),y(y){}
}p[N],q[N],ch[N];
int o[N],f[N];
typedef point pointt;
pointt operator -(point a,point b)
{
return point(a.x-b.x,a.y-b.y);
}
int dcmp(double x)
{
if(fabs(x)<eps) return ;
return x<?-:;
}
double cross(point a,point b)
{
return 1.0*a.x*b.y-a.y*b.x;
}
double mul(point p0,point p1,point p2)
{
return cross(p1-p0,p2-p0);
}
double dis(point a)
{
return sqrt(1.0*a.x*a.x+a.y*a.y);
}
bool cmp(point a,point b)
{
if(dcmp(mul(q[],a,b))==)
return dis(a-q[])<dis(b-q[]);
else
return dcmp(mul(q[],a,b))>;
}
double Graham(int n)
{
if(n<=) return ;
if(n==) return *dis(q[]-q[]);
int i,k = ,top;
point tmp;
for(i = ; i < n; i++)
{
if(q[i].y<q[k].y||(q[i].y==q[k].y&&q[i].x<q[k].x))
k = i;
}
if(k!=)
{
tmp = q[];
q[] = q[k];
q[k] = tmp;
}
sort(q+,q+n,cmp);
ch[] = q[];
ch[] = q[];
top = ;
for(i = ; i < n ; i++)
{
while(top>&&dcmp(mul(ch[top-],ch[top],q[i]))<)
top--;
top++;
ch[top] =q[i];
}
ch[top+] = ch[];
double len = ;
for(i = ; i <= top ; i++)
len+=dis(ch[i]-ch[i+]);
return len;
}
int main()
{
int n,i,j,g;
int kk = ;
while(scanf("%d",&n)&&n)
{
for(i = ; i <n ;i++)
scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].vi,&p[i].li);
int num;
int ans = INF;
double res = ;
for(i = ; i < (<<n) ; i++)
{
g = ;
int gg = ;
int tv = ;
double tlen = ;
for(j = ;j < n; j++)
{
if((<<j)&i)
{
f[gg++] = j;
tlen+=p[j].li;
tv += p[j].vi;
}
else q[g++] = p[j];
}
double len = Graham(g);
if(dcmp(tlen-len)>=)
{
if(ans>tv||(ans==tv&&num>gg))
{
ans = tv;
num = gg;
res = tlen-len;
//cout<<len<<" "<<i<<endl; for(j = ; j < gg ; j++)
o[j] = f[j]+;
}
}
}
if(kk) puts("");
printf("Forest %d\n",++kk);
printf("Cut these trees: ");
for(i = ; i < num-; i++)
printf("%d ",o[i]);
if(num)
printf("%d\n",o[num-]);
printf("Extra wood: %.2f\n",res);
}
return ;
}