题解：UVA811 The Fortified Forest

看到第一眼：限制这么强？好神秘啊。

第二眼：$N \le 15$。哦唐诗吧。

$N$ 这么小直接暴力就行了，$2^n$ 枚举出当前选中的点集，对于没有选中的点集跑凸包模板。做完了。

时间复杂度 $O(n(\log n+2^n))$。

评紫的原因难道是代码一坨吗？输出格式贼恶心。

```cpp
#include<bits/stdc++.h>
#define int long long
#define doule long double
#define inf 1e18
using namespace std;
const int N=20;
inline int read(){
    int x=0,f=1;
    char c=getchar();
    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;
}
int n,flag[N],vis[N],ans,ansnum,cnt;
double ex;
struct zyx{int x,y,v,l,loc;}a[N];
bool cmp(zyx a,zyx b){return a.x<b.x||(a.x==b.x&&a.y<b.y);}
double dis(int fir,int sec){
    return sqrtl((a[fir].x-a[sec].x)*(a[fir].x-a[sec].x)+(a[fir].y-a[sec].y)*(a[fir].y-a[sec].y));
}
vector<int> v,output;
double Andrew(){
    v.clear();
    int temp=0;
    for(int i=1;i<=n;i++)
        if(!flag[i])temp++;
    if(temp==1){
        for(int i=1;i<=n;i++){
            if(!flag[i]){
                v.push_back(i);
                return 0;
            }
        }
    }
    else if(temp==2){
        int x=114514;
        for(int i=1;i<=n;i++){
            if(flag[i])continue;
            v.push_back(i);
            if(x==114514)x=i;
            else return dis(x,i)*2;
        }
    }
    v.clear();
    for(int i=1;i<=n;i++){
        if(flag[i])continue;
        int nx=a[i].x,ny=a[i].y;
        while(1){
            if((int)v.size()<=1)break;
            int xf=a[v[v.size()-2]].x,yf=a[v[v.size()-2]].y;
            int xs=a[v.back()].x,ys=a[v.back()].y;
            if((ny-ys)*(xs-xf)<=(ys-yf)*(nx-xs))v.pop_back();
            else break;
        }
        v.push_back(i);
    }
    for(int i=1;i<=n;i++)vis[i]=0;
    for(int i=1;i<(int)v.size();i++)vis[v[i]]=1;
    int t=v.size();
    for(int i=n-1;i>=1;i--){
        if(flag[i]||vis[i])continue;
        int nx=a[i].x,ny=a[i].y;
        while(1){
            if((int)v.size()<=t)break;
            int xf=a[v[v.size()-2]].x,yf=a[v[v.size()-2]].y;
            int xs=a[v.back()].x,ys=a[v.back()].y;
            if((ny-ys)*(xs-xf)<=(ys-yf)*(nx-xs))v.pop_back();
            else break;
        }
        v.push_back(i);
    }
    double ans=0;
    for(int i=0;i<(int)v.size()-1;i++)ans+=dis(v[i],v[i+1]);
    v.pop_back();
    return ans;
}
void sol(){
    n=read();
    ans=inf;
    if(n==0)exit(0);
    if(cnt!=0)cout<<'\n';
    for(int i=1;i<=n;i++)
        a[i]=(zyx){read(),read(),read(),read(),i};
    sort(a+1,a+1+n,cmp);
    for(int i=0;i<(1<<n);i++){
        int sum=0,value=0,num=0;
        for(int j=1;j<=n;j++){
            if(i&(1<<(j-1))){
                value+=a[j].v,sum+=a[j].l,num++;
                flag[j]=1;
            }
            else flag[j]=0;
        }//选中的点是被砍掉的
        double res=Andrew();
        if(sum>=res){
            if(value<ans||(value==ans&&num<ansnum)){
                ans=value;
                ansnum=num;
                output.clear();
                ex=sum-res;
                for(int j=1;j<=n;j++)
                    if(i&(1<<(j-1)))output.push_back(a[j].loc);
            }
        }
    }
    sort(output.begin(),output.end());
    cout<<"Forest "<<++cnt<<'\n';
    cout<<"Cut these trees:";
    for(int i=0;i<(int)output.size();i++)cout<<" "<<output[i];
    cout<<'\n';
    cout<<"Extra wood: ";
    cout<<fixed<<setprecision(2)<<ex<<'\n';
}
signed main(){
    while(1)sol();
    return 0;
}
```

正在渲染内容...