1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
| #include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
using namespace std;
#define ll long long
#define Vector Point
const double eps = 1e-12;
const int N = 1e4+10;
int syn(double x)
{
if(fabs(x)<eps)return 0;
if(x>0)return 1;
else return -1;
}
struct Point{
double x,y;
}p[N],s[N];
Vector operator - (Point a,Point b){return {b.x-a.x,b.y-a.y};}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double dis(Point a,Point b){return sqrt((b.x-a.x)*(b.x-a.x)+(b.y-a.y)*(b.y-a.y));}
bool cmp(Point p1,Point p2)
{
double tmp=(Cross(p[0]-p1,p[0]-p2));
if(tmp>0)return 1;
if(tmp==0&&(dis(p1,p[0])>dis(p2,p[0])))return true;
}
double getConvexHull(int n)
{
if(n==0)return 0;
for(int i=0;i<n;i++)
{
if(i!=0&&p[i].y<p[0].y)
{
swap(p[i],p[0]);
}
}
sort(p+1,p+n,cmp);
double ans = 0;
int tot = 0;
s[0]=p[0];
for(int i=1;i<n;i++)
{
while(tot>0&&Cross(s[tot]-s[tot-1],p[i]-s[tot])<=0)tot--;
tot++;
s[tot]=p[i];
}
s[tot+1]=p[0];
for(int i=0;i<=tot;i++)
ans+=dis(s[i],s[i+1]);
return ans;
}
struct tree{
double x,y;
int vi,li;
}t[20];
int main()
{
int n;
int cas = 1;
while(~scanf("%d",&n)!=EOF&&n!=0)
{
int ans,minn=999999;
int cuttreenum = 999999;
double remain;
for(int i=0;i<n;i++)scanf("%lf %lf %d %d",&t[i].x,&t[i].y,&t[i].vi,&t[i].li);
for(int i=0;i<(1<<n);i++)
{
double P = 0;
int val = 0;
int count = 0;
int cnt = 0;
int k = i;
for(int j=0;j<n;j++)
{
if(k&1)p[count++]={t[j].x,t[j].y};
else P+=t[j].li,val+=t[j].vi;
k>>=1;
}
double x;
if(val>minn)continue;
else if(count==1||count ==0)
{
x=0;
}
else if(count==2)
{
x=2*dis(p[0],p[1]);
}
else
x=getConvexHull(count);
if(syn(P-x)>=0)
{
if(syn(val-minn)<0){
minn=val;
ans=i;
remain=P-x;
cuttreenum=count;
}
if(syn(val-minn)==0)
{
if(cuttreenum>count)
{
minn=val;
ans=i;
remain=P-x;
cuttreenum=count;
}
}
}
}
printf("Forest %d\n",cas++);
printf("Cut these trees:");
for(int i=1;i<=n;i++)
{
if(ans%2==0)printf(" %d",i);
ans>>=1;
}
printf("\nExtra wood: %.2f\n\n",remain);
}
}
|