POJ 1873 凸包+枚举

题意：一片森林，每棵树有坐标，做成栅栏的长度，本身价值，让求砍下任意棵树做成栅栏将剩下的树围上，要求被砍的这些树价值和最小，价值相同时要求被砍下的树最少，输出被砍的树，和做完栅栏后剩余的长度。

这题就用位运算枚举，最高的复杂度不过2的15次方。1的状态表示被砍的，0的状态表示剩下的。需要注意的是凸包求的是三个点以上的，那么0个点，1个点，2个点的情况需要特判。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
typedef double PointType;
struct point
{
    PointType x,y;
};
struct tree
{
    point coor;
    double val,length;
};
point data[105],stack[105],MinA;
int top;
tree tdata[20];
PointType Direction(point pi,point pj,point pk) //判断向量PiPj在向量PiPk的顺逆时针方向 +顺-逆0共线
{
    return (pj.x-pi.x)*(pk.y-pi.y)-(pk.x-pi.x)*(pj.y-pi.y);
}
PointType Dis(point a,point b)
{
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
}
bool cmp(point a,point b)
{
    PointType k=Direction(MinA,a,b);
    if(k>0) return 1;
    if(k<0) return 0;
    return Dis(MinA,a)>Dis(MinA,b);
}
void Graham_Scan(point *a,int numa)
{
    if(numa==0||numa==1)
    {
        top=0;
        return;
    }
    if(numa==2)
    {
        top=2;
        stack[0]=data[0],stack[1]=data[1];
        return;
    }
    for(int i=0; i<numa; 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]);
    MinA=a[0],top=0;
    sort(a+1,a+numa,cmp);
    stack[top++]=a[0],stack[top++]=a[1],stack[top++]=a[2];
    for(int i=3; i<numa; i++)
    {
        while(Direction(stack[top-2],stack[top-1],a[i])<0)
            top--;
        stack[top++]=a[i];
    }
}
int main()
{
    int n,numans,ans,s=0;
    double sumval,anslen;
    while(~scanf("%d",&n),n)
    {
        sumval=1e9;
        for(int i=0; i<n; i++)
            scanf("%lf%lf%lf%lf",&tdata[i].coor.x,&tdata[i].coor.y,&tdata[i].val,&tdata[i].length);
        for(int i=1; i<(1<<n)-1; i++)
        {
            int k=i,nownum=0;
            double nowsum=0,sumlen=0,nowval=0;
            for(int j=0; j<n; j++)
            {
                if(k&1)
                    sumlen+=tdata[j].length,nowval+=tdata[j].val;
                else
                    data[nownum++]=tdata[j].coor;
                k>>=1;
            }
            Graham_Scan(data,nownum);
            for(int q=0; q<top; q++)
                nowsum+=Dis(stack[q],stack[(q+1)%top]);
            if(sumlen>=nowsum&&(nowval<sumval||(nowval==sumval&&n-nownum<numans)))
                ans=i,numans=n-nownum,sumval=nowval,anslen=sumlen-nowsum;
        }
        if(s)
            printf("\n");
        printf("Forest %d\n",++s),printf("Cut these trees:");
        for(int i=0; i<n; i++)
        {
            if(ans&1)
                printf(" %d",i+1);
            ans>>=1;
        }
        printf("\nExtra wood: %.2f\n",anslen);
    }
    return 0;
}