The Fortified Forest(poj1873位运算枚举+凸包)
题意：给你一些树的坐标，价值和砍掉每棵树所能做成的篱笆长度，求出砍掉最小价值的树，然后砍掉的树能做成篱笆，能把剩下的树围起来，并求出围成以后剩余的长度
思路：因为最多15棵树，用位运算枚举每个状态一共2^15-1个状态，都用01表示假如有3棵树那么所有的状态为0~7，也就是000~111代表每一棵树是否被砍掉，每取一个状态
记录被砍的树木的价值之和，篱笆长度之和，还有砍倒的树的数量，最后砍完剩下的树木的坐标，然后对这些坐标求凸包，再求凸包的周长，用这个周长和篱笆长度比较，看砍倒的树木的长度能否围篱笆，如果能，比较树木的价值，价值小的保存其，价值，篱笆长度，凸包的周长，砍树的数量，还有状态(那些树木被砍)，价值一样的，看砍倒树木的数量，要其数量少的。
这里有个剪枝：
就是当前砍倒树木的价值大于最小的价值的时候就不要求凸包了
还要注意一点：
求凸包最少要三个点，并且是不公线的点，所以当砍得只剩下一颗或没有的时候就不用围篱笆了，这点容易wa，有这种情况，有一棵树价值大并且长度长，但是你把剩下的都砍掉也超不过它的价值，所以就选择不围围墙了，留着最大的树把其他都砍了，长度就是你砍的所有树的长度之和，砍得省下两颗的时候就是他们距离的二倍。
最后用保存的状态还原，用篱笆长度-凸包长度就是结果
#include<iostream>#include<cstdio>#include<cstring>#include<cmath>#include<vector>#include<algorithm>using namespace std;struct Point {double x,y;double v,L;Point(double x = 0,double y = 0) : x(x),y(y) {}};typedef Point Vector;Vector operator + (Vector a,Vector b) { return Vector(a.x+b.x,a.y+b.y) ;}Vector operator - (Vector a,Vector b) { return Vector(a.x-b.x,a.y-b.y) ;}Vector operator * (Vector a,double p) { return Vector(a.x*p,a.y*p) ;}Vector operator / (Vector a,double p) { return Vector(a.x/p,a.y/p) ;}const double eps = 1e-9;const double PI = acos(-1.0);double Dot(Vector a,Vector b) { return a.x*b.x + a.y*b.y ;}double Length(Vector a) { return sqrt(Dot(a,a)) ;}double Cross(Vector a,Vector b) { return a.x*b.y - a.y*b.x ;}int dcmp(double x){if(fabs(x) < eps) return 0;else return x < 0 ? -1 : 1;}bool operator < (Point a,Point b) { return a.x < b.x || (a.x == b.x && a.y < b.y) ;}bool operator == ( Point a, Point b) { return dcmp(a.x-b.x) == 0 && dcmp(a.y-b.y) == 0 ;}double Angle(Vector a,Vector b) { return acos( Dot(a,b) / Length(a) / Length(b) ) ;}double Area(Point a,Point b,Point c) { return fabs(Cross(b-a,c-a))/2 ;} Vector Rotate(Vector a,double rad) { return Vector(a.x*cos(rad) - a.y*sin(rad),a.x*sin(rad) + a.y*cos(rad) );}Vector Normal(Vector a){double L = Length(a);return Vector(-a.y/L,a.x/L);}Point GetLineIntersection(Point p,Vector v,Point q,Vector w){Vector u = p - q;double t = Cross(w,u) / Cross(v,w);return p + v*t;}bool SegmentProperIntersection(Point a1,Point a2,Point b1,Point b2){double c1 = Cross(a2-a1,b1-a1) ,c2 = Cross(a2-a1,b2-a1),c3 = Cross(b2-b1,a1-b1),c4 = Cross(b2-b1,a2-b1);return dcmp(c1)*dcmp(c2) < 0 && dcmp(c3) *dcmp(c3) < 0;}bool OnSengment(Point p,Point a,Point b){return dcmp(Cross(p-a,b-a)) == 0 && dcmp(Dot(a-p,b-p) < 0);}double PolyArea(Point *p,int n){double area = 0;int i;for(i = 0; i < n; i++){area += Cross(p[i]-p[0],p[i+1]-p[0]);}return area/2;}int Chell(Point *p,int n,Point *ch){int i,m = 0;sort(p,p+n);for(i = 0; i < n;i++){while(m > 1 && Cross( ch[m-1] - ch[m-2],p[i] - ch[m-2]) <= 0) m--;ch[m++] = p[i];}int k = m;for(i = n-2; i >= 0; i--){while(m > k && Cross(ch[m-1] - ch[m-2],p[i] - ch[m-2] ) <= 0) m--;ch[m++] = p[i];}if(n > 1) m--;return m;}double LengthChell(Point * ch,int n){double ans = 0;int i;for(i = 0; i < n; i++){ans += Length(ch[i]-ch[(i+1)%n]);}return ans;}Point p[20];Point Pv[20];double Min(double a,double b){return a > b ? a : b;}int main(){int n,cas = 1;while(scanf("%d",&n) != EOF){if(n == 0) break;int i,j;for(i = 0; i < n; i++){scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].v,&p[i].L);}double Minv = 999999,MinL = 999999,fl = 0;int flag,num = 0;for(i = 0; i < (1 << n); i++){int k = i,m = 0;Point g[20];double Mv = 0,ML = 0;int Mn = 0;int cnt = 0;for(j = 0; j < n; j++){if(k & 1){Mv = p[cnt].v + Mv;ML = p[cnt].L + ML;}else{Pv[m++] = p[cnt];}cnt++; k = k >> 1 ;}Mn = n-m;double L = 0;if(Mv > Minv)continue;if(m == 1 || m == 0)L = 0;else if(m == 2)L = 2 * Length(Pv[0]-Pv[1]);else{int temp = Chell(Pv,m,g); L = LengthChell(g,temp);}if(dcmp(ML - L) >= 0){if(dcmp(Mv-Minv) < 0) { Minv = Mv; MinL = ML; num = Mn;flag = i;fl = L;}if(dcmp(Mv-Minv) == 0) {if(dcmp(Mn - num) < 0){MinL = ML;Mn = num;flag = i;fl = L;}}}}printf("Forest %d\n",cas++);printf("Cut these trees:");int sum = 0;while(flag){if(flag & 1)printf(" %d",sum+1);sum++; flag = flag >> 1;}printf("\n");printf("Extra wood: %.2f\n\n",MinL-fl);}return 0;}