1 #include <iostream>  2 #include<cstdio>  3 #include<cstring>  4 #include<algorithm>  5 #include<stdlib.h>  6 #include<vector>  7 #include<cmath>  8 #include<queue>  9 #include<set> 10 using namespace std; 11 #define N 20 12 #define LL long long 13 #define INF 0xfffffff 14 const double eps = 1e-8; 15 const double pi = acos(-1.0); 16 const double inf = ~0u>>2; 17 struct point 18 { 19     int x,y; 20     int vi,li; 21     point(int x=0,int y=0):x(x),y(y){} 22 }p[N],q[N],ch[N]; 23 int o[N],f[N]; 24 typedef point pointt; 25 pointt operator -(point a,point b) 26 { 27     return point(a.x-b.x,a.y-b.y); 28 } 29 int dcmp(double x) 30 { 31     if(fabs(x)<eps) return 0; 32     return x<0?-1:1; 33 } 34 double cross(point a,point b) 35 { 36     return 1.0*a.x*b.y-a.y*b.x; 37 } 38 double mul(point p0,point p1,point p2) 39 { 40     return cross(p1-p0,p2-p0); 41 } 42 double dis(point a) 43 { 44     return sqrt(1.0*a.x*a.x+a.y*a.y); 45 } 46 bool cmp(point a,point b) 47 { 48     if(dcmp(mul(q[0],a,b))==0) 49         return dis(a-q[0])<dis(b-q[0]); 50     else 51         return dcmp(mul(q[0],a,b))>0; 52 } 53 double Graham(int n) 54 { 55     if(n<=1) return 0; 56     if(n==2) return 2*dis(q[0]-q[1]); 57     int i,k = 0,top; 58     point tmp; 59     for(i = 0 ; i < n; i++) 60     { 61         if(q[i].y<q[k].y||(q[i].y==q[k].y&&q[i].x<q[k].x)) 62             k = i; 63     } 64     if(k!=0) 65     { 66         tmp = q[0]; 67         q[0] = q[k]; 68         q[k] = tmp; 69     } 70     sort(q+1,q+n,cmp); 71     ch[0] = q[0]; 72     ch[1] = q[1]; 73     top = 1; 74     for(i = 2; i < n ; i++) 75     { 76         while(top>0&&dcmp(mul(ch[top-1],ch[top],q[i]))<0) 77             top--; 78         top++; 79         ch[top] =q[i]; 80     } 81     ch[top+1] = ch[0]; 82     double len = 0; 83     for(i = 0 ; i <= top ; i++) 84     len+=dis(ch[i]-ch[i+1]); 85     return len; 86 } 87 int main() 88 { 89     int n,i,j,g; 90     int kk = 0; 91     while(scanf("%d",&n)&&n) 92     { 93         for(i = 0 ; i <n ;i++) 94         scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].vi,&p[i].li); 95         int num; 96         int ans = INF; 97         double res = 0; 98         for(i = 0 ; i < (1<<n) ; i++) 99         {100             g = 0;101             int gg = 0;102             int tv = 0;103             double tlen = 0;104             for(j = 0 ;j < n; j++)105             {106                 if((1<<j)&i)107                 {108                     f[gg++] = j;109                     tlen+=p[j].li;110                     tv += p[j].vi;111                 }112                 else q[g++] = p[j];113             }114             double len = Graham(g);115             if(dcmp(tlen-len)>=0)116             {117                 if(ans>tv||(ans==tv&&num>gg))118                 {119                     ans = tv;120                     num = gg;121                     res = tlen-len;122                     //cout<<len<<" "<<i<<endl;123                     124                     125                     for(j = 0 ; j < gg ; j++)126                     o[j] = f[j]+1;127                 }128             }129         }130         if(kk) puts("");131         printf("Forest %d\n",++kk);132         printf("Cut these trees: ");133         for(i = 0; i < num-1; i++)134         printf("%d ",o[i]);135         if(num)136         printf("%d\n",o[num-1]);137         printf("Extra wood: %.2f\n",res);138     }139     return 0;140 }