1 // 凸包模板 POJ1873
2 // n=15所以可以按位枚举求凸包，再记录数据
3
4 #include <iostream>
5 #include <cstdio>
6 #include <cstdlib>
7 #include <algorithm>
8 #include <vector>
9 #include <math.h>
10 using namespace std;
11 #define LL long long
12 typedef pair<int,int> pii;
13 const double inf = 0x3f3f3f3f;
14 const LL MOD =100000000LL;
15 const int N =110;
16 #define clc(a,b) memset(a,b,sizeof(a))
17 const double eps = 1e-8;
18 void fre() {freopen("in.txt","r",stdin);}
19 void freout() {freopen("out.txt","w",stdout);}
20 inline int read() {int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();}while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}return x*f;}
21
22 int sgn(double x){
23 if(fabs(x) < eps)return 0;
24 if(x < 0)return -1;
25 else return 1;
26 }
27
28 struct Point{
29 double x,y;
30 Point(){}
31 Point(double _x,double _y){
32 x = _x;y = _y;
33 }
34 Point operator -(const Point &b)const{
35 return Point(x - b.x,y - b.y);
36 }
37 double operator ^(const Point &b)const{
38 return x*b.y - y*b.x;
39 }
40 double operator *(const Point &b)const{
41 return x*b.x + y*b.y;
42 }
43 friend bool operator<(const Point &a,const Point &b){
44 if(fabs(a.y-b.y)<eps) return a.x<b.x;
45 return a.y<b.y;
46 }
47 friend double dis2(Point a){
48 return a.x*a.x+a.y*a.y;
49 }
50 };
51
52 double dis(Point a,Point b){
53 return sqrt(dis2(a-b));
54 }
55 double mult(Point a,Point b,Point o){
56 return (a.x-o.x)*(b.y-o.y)>=(b.x-o.x)*(a.y-o.y);
57 }
58
59 Point P[16];
60 double v[16],l[16];
61
62 double graham(Point p[],int n,Point q[]){
63 int top=1;
64 sort(p,p+n);
65 if(n==0) return 0;
66 q[0]=p[0];
67 if(n==1) return 0;
68 q[1]=p[1];
69 if(n==2) return dis(p[0],p[1])*2;
70 q[2]=p[2];
71 for(int i=2;i<n;i++){
72 while(top&&(mult(p[i],q[top],q[top-1]))) top--;
73 q[++top]=p[i];
74 }
75 int len=top;
76 q[++top]=p[n-2];
77 for(int i=n-3;i>=0;i--){
78 while(top!=len&&(mult(p[i],q[top],q[top-1]))) top--;
79 q[++top]=p[i];
80 }
81 double c=dis(q[0],q[top-1]);
82 for(int i=0;i<top-1;i++)
83 c+=dis(q[i],q[i+1]);
84 return c;
85 }
86
87 int n;
88 int b[16],a[16];
89 Point p[16],ch[16];
90 int main(){
91 int cas=1;
92 while(~scanf("%d",&n),n){
93 for(int i=0;i<n;i++){
94 double x,y;
95 scanf("%lf%lf%lf%lf",&x,&y,&v[i],&l[i]);
96 P[i]=Point(x,y);
97 }
98 int k,cnt;
99 double ans=0;
100 int minn_cnt=11111;
101 double sum,len,minn=inf;
102 for(int st=0;st<(1<<n);st++){
103 sum=0,len=0,k=0,cnt=0;
104
105 for(int i=0;i<n;i++){
106 if(st&(1<<i)){
107 sum+=v[i];
108 len+=l[i];
109 b[++cnt]=i+1;
110 }
111 else{
112 p[k++]=P[i];
113 }
114 }
115 double lenn=graham(p,k,ch);
116 if(lenn>len) continue;
117 if(sum<minn||(sum==minn&&cnt<minn_cnt)){
118 minn=sum;
119 minn_cnt=cnt;
120 ans=len-lenn;
121 for(int i=1;i<=cnt;i++){
122 a[i]=b[i];
123 }
124 }
125 }
126 printf("Forest %d
",cas++);
127 printf("Cut these trees:");
128 for(int i=1;i<=minn_cnt;i++){
129 printf(" %d",a[i]);
130 }
131 printf("
");
132 printf("Extra wood: ");
133 printf("%.2f
",ans);
134 printf("
");
135 }
136 return 0;
137 }
