POJ 1873 The Fortified Forest [凸包 枚举]

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
const int N=1005,INF=1e9;
const double eps=1e-8;
const double pi=acos(-1);

inline int read(){
    char c=getchar();int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}
    return x*f;
}

inline int sgn(double x){
    if(abs(x)<eps) return 0;
    else return x<0?-1:1;
}

struct Vector{
    double x,y;
    Vector(double a=0,double b=0):x(a),y(b){}
    bool operator <(const Vector &a)const{
        //return x<a.x||(x==a.x&&y<a.y);
        return sgn(x-a.x)<0||(sgn(x-a.x)==0&&sgn(y-a.y)<0);
    }
};
typedef Vector Point;
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 b){return Vector(a.x*b,a.y*b);}
Vector operator /(Vector a,double b){return Vector(a.x/b,a.y/b);}
bool operator ==(Vector a,Vector b){return sgn(a.x-b.x)==0&&sgn(a.y-b.y)==0;}

double Dot(Vector a,Vector b){return a.x*b.x+a.y*b.y;}
double Cross(Vector a,Vector b){return a.x*b.y-a.y*b.x;}
double DisPP(Point a,Point b){
    Point t=b-a;
    return sqrt(t.x*t.x+t.y*t.y);
}

int cas=0;
int n,x,y,v[N],l[N];
double ans;
Point p[N],ch[N],rp[N];
int rn;

double ConvexHull(Point p[],int n,Point ch[]){
    sort(p+1,p+1+n);
    int m=0,cnt=0;
    for(int i=1;i<=n;i++) {
        while(m>1&&sgn(Cross(ch[m]-ch[m-1],p[i]-ch[m-1]))<=0) m--;
        ch[++m]=p[i];
    }
    int k=m;
    for(int i=n-1;i>=1;i--) {
        while(m>k&&sgn(Cross(ch[m]-ch[m-1],p[i]-ch[m-1]))<=0) m--;
        ch[++m]=p[i];
    }
    if(n>1) m--;
    double ans=0;
    for(int i=1;i<=m;i++) ans+=DisPP(ch[i],ch[i%m+1]);
    return ans;
}

void solve(){
    int ansV=INF,ansS=0,ansCnt=INF,S=(1<<n);
    double extra;
    for(int i=1;i<S;i++){
        double len=0;
        int val=0,cnt;
        rn=0;
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                j++;
                len+=l[j],val+=v[j],cnt++;
                j--;
            }else rp[++rn]=p[j+1];
        }
        if(val>ansV||(val==ansV&&cnt>ansCnt)) continue;
        double peri=ConvexHull(rp,rn,ch);
        if(sgn(peri-len)>0) continue;
        if(val<ansV||(val==ansV&&cnt<ansCnt)){
            ansV=val;
            ansS=i;
            ansCnt=cnt;
            extra=len-peri;
        }
    }
    printf("Forest %d\nCut these trees: ",++cas);
    for(int j=0;j<=16;j++) if(ansS&(1<<j)) printf("%d ",j+1);
    printf("\nExtra wood: ");
    printf("%.2f\n\n",extra);
}

int main(int argc, const char * argv[]) {
    while(scanf("%d",&n)!=EOF&&n){
        for(int i=1;i<=n;i++) p[i].x=read(),p[i].y=read(),v[i]=read(),l[i]=read();
        solve();
    }
    return 0;
}