POJ1873+几何凸包

简单凸包+暴力枚举。

/*
几何凸包+暴力
*/
#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#include<queue>
#include<stack>
#include<map>
#include<set>
using namespace std;
typedef long long int64;
//typedef __int64 int64;
typedef pair<int64,int64> PII;
#define MP(a,b) make_pair((a),(b)) 
const int inf = 0x3f3f3f3f;
const double pi=acos(-1.0);
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
const double eps = 1e-8;
const int maxm = 1005;
const int maxn = 16;

struct Point2 {
	int x,y;
	double val,len;
	bool ok;//ok = true 需要去掉的点
}pnt[ maxn ];
int cur[ maxn ];
int cnt_cur;
double val_cur,ans1;
int best[ maxn ];
int cnt_best;
double val_best,ans2;
double Len1,Len2;
struct Point {
	double x,y;
	bool operator < ( const Point &t ) const {
		return y<t.y||( y==t.y&&x<t.x );
	}
}a[ maxn ],res[ maxn ];

double xmult( Point sp,Point ep,Point op ){
	return (sp.x-op.x)*(ep.y-op.y)-(sp.y-op.y)*(ep.x-op.x);
}

double dist( int i,int j ){
	return sqrt( (res[i].x-res[j].x)*(res[i].x-res[j].x)+(res[i].y-res[j].y)*(res[i].y-res[j].y) );
}

int Graham( int n ){
	int top = 1;
	sort( a,a+n );
	if( n==0 ) return 0;
	else res[0] = a[0];
	if( n==1 ) return 1;
	else res[1] = a[1];
	if( n==2 ) return 2;
	else res[2] = a[2];
	for( int i=2;i<n;i++ ){
		while( top>0 && xmult(res[top],res[top-1],a[i])>=0 )
			top--;
		res[ ++top ] = a[i];
	}
	int len = top;
	res[ ++top ] = a[ n-2 ];
	for( int i=n-3;i>=0;i-- ){
		while( top!=len && xmult( res[top],res[top-1],a[i])>=0 )
			top--;
		res[ ++top ] = a[i];
	}
	return top;
} 

bool Solve( int n ){
	double temp1 = 0;
	int cc = 0;
	for( int i=0;i<n;i++ ){
		  if( pnt[i].ok==false ){
		  	a[ cc ].x = 1.0*pnt[ i ].x;
		  	a[ cc ].y = 1.0*pnt[ i ].y;
		  	cc++;
		  }
		  else temp1 += pnt[ i ].len;
	}
	int q = cc;
	cc = Graham( q );
	double temp2 = 0;
	res[ cc ] = res[ 0 ];
	for( int i=0;i<cc;i++ ){
		temp2 += dist( i,i+1 );
	}
	ans1 = temp2;
	Len1 = temp1;
	if( temp2<=temp1 ) return true;
	else return false;
}
	
int main(){
	int n;
	int Case = 1;
	while( scanf("%d",&n),n ){
		if( Case!=1 ) printf("\n");
		for( int i=0;i<n;i++ ){
			scanf("%d%d%lf%lf",&pnt[i].x,&pnt[i].y,&pnt[i].val,&pnt[i].len);
		}
		int N = (1<<n);
		ans1 = ans2 = 0;
		val_best = 9999999999.0;
		for( int i=0;i<N;i++ ){
			cnt_cur = 0;
			val_cur = 0;
			for( int j=0;j<n;j++ ){
				if( i&(1<<j) ){
					cur[ cnt_cur++ ] = j;
					pnt[ j ].ok = true;
					val_cur += pnt[ j ].val;
				}
				else
					pnt[ j ].ok = false;
			}
			if( cnt_cur==n ) continue;
			if( Solve(n)==true ){
				//printf("Solve\n");
				 if( val_cur<val_best ){
				 	val_best = val_cur;
				 	for( int k=0;k<cnt_cur;k++ ){
				 		best[ k ] = cur[ k ];
				 	}
				 	cnt_best = cnt_cur;
				 	ans2 = ans1;
				 	Len2 = Len1;
				 }
				 else if( val_cur==val_best ){
				 	if( cnt_cur<cnt_best ){
				 		for( int k=0;k<cnt_cur;k++ ){
				 			best[ k ] = cur[ k ];
				 		}
				 		cnt_best = cnt_cur;
				 		ans2 = ans1;
				 		Len2 = Len1;
				 	}
				 }
			}
		}
		printf("Forest %d\n",Case++);
		printf("Cut these trees: ");
		for( int i=0;i<cnt_best;i++ )
			printf("%d ",best[i]+1);
		printf("\n");
		printf("Extra wood: %.2lf\n",Len2-ans2);
	}
	return 0;
}