poj1873 The Fortified Forest 凸包+枚举 水题

/*
poj1873 The Fortified Forest 凸包+枚举 水题
用小树林的木头给小树林围一个围墙
每棵树都有价值
求消耗价值最低的做法，输出被砍伐的树的编号和剩余的木料
若砍伐价值相同，则取砍伐数小的方案。
*/
#include<stdio.h>
#include<math.h>
#include <algorithm> 
#include <vector>
using namespace std;
const double eps = 1e-8;  
struct point
{
	double x,y;
};
struct exinfo
{
	int v,l;
}info[20];
int n;
point dian[20],zhan[20];
//////////////////////////////////////////////////
point *mo_dian;
double mo_distance(point p1,point p2)
{
    return sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y));
}
double mo_xmult(point p2,point p0,point p1)//p1在p2左返回负，在右边返回正
{
    return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
}

bool mo_ee(double x,double y)
{
	double ret=x-y;
	if(ret<0) ret=-ret;
	if(ret<eps) return 1;
	return 0;
}
bool mo_gg(double x,double y)  {   return x > y + eps;} // x > y   
bool mo_ll(double x,double y)  {   return x < y - eps;} // x < y   
bool mo_ge(double x,double y) {   return x > y - eps;} // x >= y   
bool mo_le(double x,double y) {   return x < y + eps;}     // x <= y   

bool mo_cmp(point a,point b)   // 第一次排序   
{  
    if( mo_ee(a.y ,b.y ) )  
        return mo_ll(a.x, b.x);  
    return mo_ll(a.y,b.y);  
}  
bool mo_cmp1(point a,point b)  // 第二次排序   
{  
    double len = mo_xmult(b,mo_dian[0],a);  
    if( mo_ee(len,0.0) )  
        return mo_ll(mo_distance(mo_dian[0],a),mo_distance(mo_dian[0],b));  
    return mo_gg(len,0.0);  
}  
int mo_graham(int n,point *dian,point *stk)
{
	int i,top=1;
	mo_dian=dian;
	sort(mo_dian,mo_dian+n,mo_cmp);  
    sort(mo_dian+1,mo_dian+n,mo_cmp1);  
	stk[0]=mo_dian[0];  
    stk[1]=mo_dian[1];  
	for(i=2;i<n;++i)  
    {  
        while(top>0&&mo_xmult(mo_dian[i],stk[top-1],stk[top])<=0) --top;  
        stk[++top]=mo_dian[i];  
    }  
    return top+1;  
}

////////
void getpoint(int tree,point *dian,point *work,vector<int> &cut,int &n_cut,int &n_sheng,int &cutv,int &cutl)
{
	cut.clear();
	cutv=0;
	cutl=n_sheng=n_cut=0;
	int i;
	for(i=0;i<n;++i)
	{
		if((1<<i)&tree)//cut
		{
			
			cut.push_back(i);
			n_cut++;
			cutv+=info[i].v;
			cutl+=info[i].l;
		}else
		{
			work[n_sheng++]=dian[i];
		}
	}
}
double zhou(point *dian,int n)
{
	int i;
	double ret=0;
	for(i=0;i<n;++i)
	{
		ret+=sqrt(
			(dian[(i+1)%n].x-dian[i].x)*(dian[(i+1)%n].x-dian[i].x)
			+(dian[(i+1)%n].y-dian[i].y)*(dian[(i+1)%n].y-dian[i].y)
			);
	}
	return ret;
}
int main()
{
	int i,ncase=1;
	while(scanf("%d",&n),n)
	{
		for(i=0;i<n;++i)
		{
			scanf("%lf%lf%d%d",&dian[i].x,&dian[i].y,&info[i].v,&info[i].l);
		}
		int maxofi=(1<<n)-1;
		int cutvalue=999999999;
		double l_sheng;
		int cutn;
		vector<int> cut;
		vector<int> tempcut;
		point work[20];
		for(i=0;i<maxofi;++i)
		{
			int tempcutn,shengyun;
			int tempcutv,cutl;
			int ret;
			double zhouchang;
			getpoint(i,dian,work,tempcut,tempcutn,shengyun,tempcutv,cutl);
			if(shengyun==1)
			{
				zhouchang=0;
			}else if(shengyun==2)
			{
				zhouchang=mo_distance(work[0],work[1])*2;
			}else
			{
				ret=mo_graham(shengyun,work,zhan);
				zhouchang=zhou(zhan,ret);
			}
			
			if(mo_ge(cutl,zhouchang))
			{
				if(tempcutv<cutvalue)
				{
					cutvalue=tempcutv;
					l_sheng=cutl-zhouchang;
					cut=tempcut;
					cutn=tempcutn;
				}else if(tempcutv==cutvalue&&tempcutn<cutn)
				{
					cutvalue=tempcutv;
					l_sheng=cutl-zhouchang;
					cut=tempcut;
					cutn=tempcutn;
				}
			}
		}
		if(ncase!=1) printf("
");
		printf("Forest %d
",ncase++);
		printf("Cut these trees:");
		int len=cut.size();
		for(i=0;i<len;++i)
		{
			printf(" %d",cut[i]+1);
		}
		printf("
");
		printf("Extra wood: %.2lf
",l_sheng);
	}
	return 0;
}