The Fortified Forest

Time Limit: 1000MS		Memory Limit: 30000K
Total Submissions: 6115		Accepted: 1720

Once upon a time, in a faraway land, there lived a king. This king owned a small collection of rare and valuable trees, which had been gathered by his ancestors on their travels. To protect his trees from thieves, the king ordered that a high fence be built around them. His wizard was put in charge of the operation.
Alas, the wizard quickly noticed that the only suitable material
available to build the fence was the wood from the trees themselves. In
other words, it was necessary to cut down some trees in order to build a
fence around the remaining trees. Of course, to prevent his head from
being chopped off, the wizard wanted to minimize the value of the trees
that had to be cut. The wizard went to his tower and stayed there until
he had found the best possible solution to the problem. The fence was
then built and everyone lived happily ever after.

You are to write a program that solves the problem the wizard faced.

The
input contains several test cases, each of which describes a
hypothetical forest. Each test case begins with a line containing a
single integer n, 2 <= n <= 15, the number of trees in the forest.
The trees are identified by consecutive integers 1 to n. Each of the
subsequent n lines contains 4 integers xi, yi, vi, li that describe a
single tree. (xi, yi) is the position of the tree in the plane, vi is
its value, and li is the length of fence that can be built using the
wood of the tree. vi and li are between 0 and 10,000.

The input ends with an empty test case (n = 0).

For
each test case, compute a subset of the trees such that, using the wood
from that subset, the remaining trees can be enclosed in a single fence.
Find the subset with minimum value. If more than one such minimum-value
subset exists, choose one with the smallest number of trees. For
simplicity, regard the trees as having zero diameter.

Display, as shown below, the test case numbers (1, 2, ...), the
identity of each tree to be cut, and the length of the excess fencing
(accurate to two fractional digits).

Display a blank line between test cases.

6

 0  0  8  3

 1  4  3  2

 2  1  7  1

 4  1  2  3

 3  5  4  6

 2  3  9  8

3

 3  0 10  2

 5  5 20 25

 7 -3 30 32

0

Forest 1

Cut these trees: 2 4 5

Extra wood: 3.16

Forest 2

Cut these trees: 2

Extra wood: 15.00


题意:国王有一些树,他想砍掉一些树做篱笆围住剩下的树,每棵树都有坐标,价值和做成篱笆长度,我们应该使砍掉的树的价值尽可能的小并且做成的篱笆能够围住剩下的树，如果方案的价值相同选择砍掉数量
少的，最后输出砍掉的树的编号和篱笆围了之后还能剩下多少。
题解：深坑啊。。。WA了好多次，竟然是cmp函数里面的变量p[0]的函数名冲突了...world final的水题都好难。。过，但是想法不难。。就是每次枚举那些树不取和取,不超过2^15次方,用二进制表示..然后再进行凸包。。比较。。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <math.h>

#include <algorithm>

#include <stdlib.h>

using namespace std;

const double eps = 1e-;

const int N = ;

struct Point

{

    double x,y,value,len;

} p[N],q[N];

Point Stack[N];

int n;

double cross(Point a,Point b,Point c)

{

    return (a.x-c.x)*(b.y-c.y)-(a.y-c.y)*(b.x-c.x);

}

double dis(Point a,Point b)

{

    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));

}

Point po; //大坑

int cmp(Point a,Point b)

{

    if(cross(a,b,po)>) return ;

    if(cross(a,b,po)==&&dis(b,po)-dis(a,po)>eps) return ;

    return ;

}

double Graham(Point p[],int n)

{

    if(n==||n==) return ;

    if(n==) return *dis(p[],p[]);

    int k =;

    for(int i=; i<n; i++)

    {

        if(p[k].y>p[i].y||((p[k].y==p[i].y)&&(p[k].x>p[i].x))) k=i;

    }

    swap(p[],p[k]);

    po = p[];  ///嗯，这里

    int top=;

    sort(p+,p+n,cmp);

    Stack[]=p[];

    Stack[]=p[];

    Stack[]=p[];

    for(int i=; i<n; i++)

    {

        while(top>=&&cross(p[i],Stack[top],Stack[top-])>=)

        {

            top--;

        }

        Stack[++top]=p[i];

    }

    double ans = ;

    for(int i=; i<=top; i++)

    {

        ans+=dis(Stack[i],Stack[i-]);

    }

    ans+=dis(Stack[top],Stack[]);

    return ans;

}

int main()

{

    int _count = ;

    while(scanf("%d",&n)!=EOF&&n)

    {

        for(int i=; i<n; i++)

        {

            scanf("%lf%lf%lf%lf",&p[i].x,&p[i].y,&p[i].value,&p[i].len);

        }

        int t = (<<n)-;

        int cnt[N],id[N];///保存要砍掉的树的编号

        double save=;

        int num=; ///要砍掉的数的数目

        double mi=; ///保存要砍掉的树的最小价值

        for(int i=; i<t; i++) ///1代表砍掉这棵树,0代表不砍,至少要砍一棵树

        {

            double value=,len=;

            int k=,k1=;

            for(int j=; j<n; j++)

            {

                if((i>>j)&)  ///移位操作,表示当前第j+1棵树要砍掉

                {

                    cnt[k++] = j;

                    value+=p[j].value;

                    len+=p[j].len;

                }

                else q[k1++] = p[j];

            }

            double L = Graham(q,k1);

            if(len-L>eps)   ///如果能够组成的篱笆长度大于凸包周长

            {

                if(mi-value>eps||(fabs(value-mi)<eps&&k<num))

                {

                    mi = value;

                    for(int j=; j<k; j++) id[j]=cnt[j];

                    num = k;

                    save = len - L;

                }

            }

        }

        printf("Forest %d\nCut these trees: ",_count++);

        for(int i=; i<num; i++)

        {

            printf("%d ",id[i]+);

        }

        printf("\nExtra wood: %.2lf\n\n",save);

    }

    return ;

}