Poj-1873 The Fortified Forest（凸包+枚举）

传送门：(p≧w≦q)

分析都在注释里↓

/* 
题意 
n棵树，每棵树都有价值和长度，砍一些树把剩下的树围起来（相当于凸包边长），要求花费的价值最小。
优先砍价值小的树，在消耗价值相等的情况下选择砍掉数量最少的方案。
解法 
求凸包模板+ 价值从小到大排序，枚举砍树  
*/ 


#include <cstdio>
#include <iostream>
#include <cmath>
#include <vector>
#include <string.h>  
#include <algorithm>
const double pi = acos(-1.0);
const int maxn = 100;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
using namespace std;
struct Point{
	double x,y,v,l;
	Point(double x = 0,double y = 0,double v = 0,double l = 0):x(x),y(y),v(v),l(l){}
};
int n;
typedef Point Vector;
Point lst[maxn];
vector<Point> a;
int stk[maxn],top;
Vector operator - (Point A,Point B)
{
	return Vector(A.x - B.x,A.y - B.y);
}
int sgn(double x)
{
	if(fabs(x) < eps)
		return 0;
	if(x < 0)
		return -1;
	return 1;
}
double Cross(Vector v0,Vector v1,Vector v2)//叉积 
{
	return (v1.x-v0.x)*(v2.y-v0.y)-(v1.y-v0.y)*(v2.x-v0.x);
}
double Dis(Point p1,Point p2)//两点距离 
{
	return sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
}
bool cmp(Point p1,Point p2)//逆时针排序 
{
	int tmp = Cross(a[0],p1,p2);
	if(tmp > 0)
	{
		return true;
	}
	if(tmp == 0 && Dis(a[0],p1) < Dis(a[0],p2))
	{
		return true;
	}
	return false;
}
double Graham(int len)//返回剩余的树长 
{
	if(a.size() == 1) 
		return len;//剩一棵树 不用围 
	else if(a.size() == 2)
		return len - Dis(a[0],a[1])*2;//只剩两棵，最小周长为两点距离的2倍 
	for(int i = 1;i < a.size();i++)
	{
		if(a[i].y < a[0].y || (a[i].y == a[0].y && a[i].x < a[0].x))//从小到大 
		swap(a[i],a[0]);
	}
	sort(a.begin()+1,a.end(),cmp);//级角排序 
	vector<Point> s;
	s.push_back(a[0]);
	s.push_back(a[1]);
	s.push_back(a[2]);
	for(int i = 3;i< a.size();i++)
	{
        while(s.size() >= 2 && Cross(s[s.size()-2],s[s.size()-1],a[i]) < eps)
            s.pop_back();
        s.push_back(a[i]);
    }
    s.push_back(s[0]);
    double ans = 0;
    //求凸包周长
    for(int i = 0;i < s.size() - 1;i++)
        ans += Dis(s[i],s[i+1]);
    return len - ans;
}
int main()
{
	int n,cas = 0;
	while(~scanf("%d",&n)&&n)
	{
		
		for(int i = 0;i < n;i++)
		{
			scanf("%lf%lf%lf%lf",&lst[i].x,&lst[i].y,&lst[i].v,&lst[i].l);
		}
		double bv = inf,bn,bs;//最优情况下的 代价，砍的数量，最优状态 
		double be = 0;//剩下的树 
		for(int i = 1;i <(1<<n) - 1;i++)//枚举的过程 
		{
			int tv = 0,tl = 0;//目前的 价值，树长 
			a.clear();
			for(int j = 0;j < n;j++)
			{
				if(!((1<<j)&i))
				a.push_back(lst[j]);
				else
				{
					tl += lst[j].l;
					tv += lst[j].v;
				}
			} 
			if(tv > bv)
			continue;
			double extra = Graham(tl);
			if(extra >= 0)//<0则这种情况不够围  无法达成 
			{
				if(tv < bv)
				{
					bv = tv;
					bn = n - a.size();
					bs = i;
					be = extra;
				}
				else if(tv == bv &&n - a.size() < bn)
				{
					bn = n - a.size();
					bs = i;
					be = extra;
				}
			}
		}
		printf("Forest %d\nCut these trees:",++cas);
        for(int i = 0;i < n;i++)
            if((1<<i)&(int)bs)  
				printf(" %d",i+1);
        printf("\nExtra wood: %.2f\n\n",be);
    }
	return 0;
}
/*
6
 0  0  8  3
 1  4  3  2
 2  1  7  1
 4  1  2  3
 3  5  4  6
 2  3  9  8
3
 3  0 10  2
 5  5 20 25
 7 -3 30 32
0
*/