POJ1873

あなたにn個の木をあげて、すべての木はすべて自分の座標と価値、長さがあります.今は木を切って、残った木を囲んでください.
価値の安い木を優先的に切り、いくつかの木を切る案があれば価値が同じなら数が最も少ない案を選ぶ.そして価値は数量と同じように勝手に出力すればいいのです.
構想:nは比較的小さいので,dfs枚で各木の状態を挙げることができる.残りの木で凸包を使って城を囲む周長を求める.
この道は朝までかかって、うんざりして、やっと勉強しました.多くのものが使用中に問題が発生しました.例えば凸包の中のwhileを求めてifを書いて、わけがわからないで
元の配列が入れ替わって、しかもテーマが与えたデータはまだとても水で、私の問題を全然検出できなくて、自分のコードを見つめて、絶えず間違いを探していましたが、最後にやっとAになりました.

#include<stdio.h>
#include<math.h>
#include<string.h>
#include<algorithm>
using namespace std;
const int maxn=1<<16;
const int maxm=1<<29;
int n,e,k;
double sum1=0,sum2=0,sum3=0;
double maxn1=0,maxn2=0,maxn3=0;
int ans[maxn],kj[maxn];
struct node
{
    double x,y;
    double val,l;
} st[maxn],num[maxn],num2[maxn];
int cnt=0;
double dis(node p1,node p2)
{
    return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
double multi(node p1,node p2,node p3)
{
    return (p1.x-p3.x)*(p2.y-p3.y)-(p2.x-p3.x)*(p1.y-p3.y);
}
bool cmp(node p1,node p2)
{
    if(multi(p1,p2,num2[0])>0) return true;
    if(multi(p1,p2,num2[0])==0&&dis(p1,num2[0])<dis(p2,num2[0]))return true;
    return false;
}
void dfs(int cur)
{
    if(cur==n)
    {
        sum1=0,sum2=0,sum3=0;
        cnt=0;
        k=0;
        for(int i=0; i<n; i++)
        {
            if(ans[i]==0)//0      ，         
            {
                num2[cnt++]=num[i];
            }
            else
            {
                sum1+=num[i].val;
                sum2+=num[i].l;
            }
        }
        sum3=n-cnt;
        if(cnt==0||cnt==n) return;
        if(cnt==1)//           ，         。          ，     
        {
            if(maxn1>sum1)
            {
                maxn1=sum1;
                maxn2=sum2;
                maxn3=sum3;
                for(int i=0; i<n; i++)
                {
                    kj[i]=ans[i];
                }

            }
            else if(maxn1==sum1)
            {
                if(sum3<maxn3)
                {
                    maxn1=sum1;
                    maxn2=sum2;
                    maxn3=sum3;
                    for(int i=0; i<n; i++)
                        kj[i]=ans[i];
                }
            }
            return ;
        }
        double sum=0;
        if(cnt==2)//          ，   2         。     ，      。
        {
            sum=dis(num2[0],num2[1]);
            sum=2*sqrt(sum);

        }
        else
        {
            for(int i=0; i<cnt; i++)
            {
                if(num2[i].x<num2[k].x||(num2[i].x==num2[k].x&&num2[i].y<num2[k].y)) k=i;
            }
            swap(num2[0],num2[k]);
            sort(num2+1,num2+cnt,cmp);
            st[0]=num2[0];
            st[1]=num2[1];
            st[2]=num2[2];
            e=2;
            for(int i=3; i<cnt; i++)
            {
                while(e>1&&multi(num2[i],st[e],st[e-1])>=0) e--;
                st[++e]=num2[i];
            }

            for(int i=0; i<=e; i++)
                sum+=sqrt((double)dis(st[i],st[i==e?0:i+1]));
        }
        if(sum<=sum2)
        {
            if(maxn1>sum1)
            {
                /*
                for(int i=0; i<n; i++)
                    printf("%d ",ans[i]);
                puts("");
                printf("%lf %lf %lf
",maxn1,sum,sum2);
                */
                maxn1=sum1;
                maxn2=sum2-sum;
                maxn3=sum3;
                for(int i=0; i<n; i++)
                    kj[i]=ans[i];
            }
            else if(maxn1==sum1)
            {
                if(sum3<maxn3)
                {
                    maxn1=sum1;
                    maxn2=sum2-sum;
                    maxn3=sum3;
                    for(int i=0; i<n; i++)
                        kj[i]=ans[i];
                }
            }
        }
        return ;
    }
    ans[cur]=0;
    dfs(cur+1);
    ans[cur]=1;
    dfs(cur+1);
}
int main()
{
    int tt=1;
    while(scanf("%d",&n)!=EOF)
    {
        if(n==0) break;
        maxn1=maxn,maxn2=maxm;
        for(int i=0; i<n; i++)
            scanf("%lf %lf %lf %lf",&num[i].x,&num[i].y,&num[i].val,&num[i].l);
        dfs(0);
        printf("Forest %d
",tt++);
        printf("Cut these trees:");
        for(int i=0; i<n; i++)
            if(kj[i])
                printf(" %d",i+1);
        puts("");
        printf("Extra wood: %.2lf

",maxn2);
    }
    return 0;
}