凸包模板 POJ1873

 // 凸包模板 POJ1873

 // n=15所以可以按位枚举求凸包，再记录数据

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <algorithm>

 #include <vector>

 #include <math.h>

 using namespace std;

 #define LL long long

 typedef pair<int,int> pii;

 const double inf = 0x3f3f3f3f;

 const LL MOD =100000000LL;

 const int N =;

 #define clc(a,b) memset(a,b,sizeof(a))

 const double eps = 1e-;

 void fre() {freopen("in.txt","r",stdin);}

 void freout() {freopen("out.txt","w",stdout);}

 inline int read() {int x=,f=;char ch=getchar();while(ch>''||ch<'') {if(ch=='-') f=-; ch=getchar();}while(ch>=''&&ch<='') {x=x*+ch-'';ch=getchar();}return x*f;}

 int sgn(double x){

     if(fabs(x) < eps)return ;

     if(x < )return -;

     else return ;

 }

 struct Point{

     double x,y;

     Point(){}

     Point(double _x,double _y){

         x = _x;y = _y;

     }

     Point operator -(const Point &b)const{

         return Point(x - b.x,y - b.y);

     }

     double operator ^(const Point &b)const{

         return x*b.y - y*b.x;

     }

     double operator *(const Point &b)const{

         return x*b.x + y*b.y;

     }

     friend bool operator<(const Point &a,const Point &b){

         if(fabs(a.y-b.y)<eps) return a.x<b.x;

         return a.y<b.y;

     }

     friend double dis2(Point a){

         return a.x*a.x+a.y*a.y;

     }

 };

 double dis(Point a,Point b){

     return sqrt(dis2(a-b));

 }

 double mult(Point a,Point b,Point o){

     return (a.x-o.x)*(b.y-o.y)>=(b.x-o.x)*(a.y-o.y);

 }

 Point P[];

 double v[],l[];

 double graham(Point p[],int n,Point q[]){

      int top=;

      sort(p,p+n);

      if(n==) return ;

      q[]=p[];

      if(n==) return ;

      q[]=p[];

      if(n==) return dis(p[],p[])*;

      q[]=p[];

      for(int i=;i<n;i++){

          while(top&&(mult(p[i],q[top],q[top-]))) top--;

          q[++top]=p[i];

      }

      int len=top;

      q[++top]=p[n-];

      for(int i=n-;i>=;i--){

          while(top!=len&&(mult(p[i],q[top],q[top-]))) top--;

          q[++top]=p[i];

      }

      double c=dis(q[],q[top-]);

      for(int i=;i<top-;i++)

         c+=dis(q[i],q[i+]);

     return c;

 }

 int n;

 int b[],a[];

 Point p[],ch[];

 int main(){

     int cas=;

     while(~scanf("%d",&n),n){

         for(int i=;i<n;i++){

             double x,y;

             scanf("%lf%lf%lf%lf",&x,&y,&v[i],&l[i]);

             P[i]=Point(x,y);

         }

         int k,cnt;

         double ans=;

         int minn_cnt=;

         double sum,len,minn=inf;

         for(int st=;st<(<<n);st++){

             sum=,len=,k=,cnt=;

             for(int i=;i<n;i++){

                if(st&(<<i)){

                    sum+=v[i];

                    len+=l[i];

                    b[++cnt]=i+;

                }

                else{

                   p[k++]=P[i];

                }

             }

             double lenn=graham(p,k,ch);

             if(lenn>len) continue;

             if(sum<minn||(sum==minn&&cnt<minn_cnt)){

                 minn=sum;

                 minn_cnt=cnt;

                 ans=len-lenn;

                 for(int i=;i<=cnt;i++){

                     a[i]=b[i];

                 }

             }

         }

         printf("Forest %d\n",cas++);

         printf("Cut these trees:");

         for(int i=;i<=minn_cnt;i++){

             printf(" %d",a[i]);

         }

         printf("\n");

         printf("Extra wood: ");

         printf("%.2f\n",ans);

         printf("\n");

     }

     return ;

 }