The Fortified Forest POJ

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cmath>
 5 #include <algorithm>
 6 using namespace std;
 7 const double eps=1e-12;
 8 const int inf=0x3f3f3f3f;
 9 const int maxn=16;
10 struct Node{
11     int x,y,vi,li;
12     bool operator < (const Node& a)const{
13         return x<a.x||x==a.x&&y<a.y;
14     }
15     Node operator - (const Node& a){
16         return Node{x-a.x,y-a.y};
17     }
18 }p[maxn],vex[maxn],ch[maxn];
19 double getdis(Node a,Node b){
20     return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
21 }
22 int cut[maxn],ans[maxn];
23 
24 int cross(Node a,Node b){
25     return a.x*b.y-a.y*b.x;
26 }
27 
28 double ConvexHull(Node *p,int n){
29     if(n<=1) return 0;
30     sort(p,p+n);
31     int m=0;
32     for(int i=0;i<n;i++){
33         while(m>1&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
34         ch[m++]=p[i];
35     }
36     int k=m;
37     for(int i=n-2;i>=0;i--){
38         while(m>k&&cross(ch[m-1]-ch[m-2],p[i]-ch[m-2])<=0) m--;
39         ch[m++]=p[i];
40     }
41     m--;
42     double ans=getdis(ch[0],ch[m]);
43     for(int i=0;i<m;i++) ans+=getdis(ch[i],ch[i+1]);
44     return ans;
45 }
46 int main(){
47     int n,kase=0;
48     while(scanf("%d",&n)&&n){
49         if(kase) puts("");
50         for(int i=0;i<n;i++) scanf("%d%d%d%d",&p[i].x,&p[i].y,&p[i].vi,&p[i].li);
51         int sta=1<<n;
52         int minval=inf,id;
53         double res;
54         int tempval,templen;
55         for(int i=1;i<sta;i++){
56             int cnt=0,num=0;
57             tempval=0;templen=0;
58             for(int j=0;j<n;j++) if((1<<j)&i){
59                 cut[cnt++]=j;
60                 tempval+=p[j].vi;
61                 templen+=p[j].li;
62             }else {
63                 vex[num++]=p[j];
64             }
65             double dis=ConvexHull(vex,num);
66             if(templen>dis&&(tempval<minval||tempval==minval&&cnt<id)){
67                 minval=tempval;
68                 res=templen-dis;
69                 id=cnt;
70                 for(int i=0;i<cnt;i++) ans[i]=cut[i];
71             }
72         }
73         printf("Forest %d
",++kase);
74         printf("Cut these trees:");
75         for(int i=0;i<id;i++) printf(" %d",ans[i]+1);
76         printf("
Extra wood: %.2f
",res);
77     }
78     return 0;
79 }