E

题目大意：有n棵树，每棵树有坐标(x,y)，价值v，长度l，问如何砍能砍掉最小价值为的树（价值相同则砍最少的树），能把其他树都围起来
思路：枚举所有砍树的方案（我用的递归，用二进制的方法理论上来说也可以），算一下能不能围起剩下的树（如果价值比当前答案要大就不用算了）。至于怎么围起剩下的树，一个点的明显是需要0长度，两个点就需要这两个点的距离*2，三个点或以上就要用到求凸包的方法（反正我的凸包是不能算三个点以下的）

PS：输出最好复制啊，我好像就是因为forest打错了WA了好几次啊……

AC Code:

  1 #include <cstdio>
  2 #include <cmath>
  3 #include <algorithm>
  4 using namespace std;
  5 
  6 const double EPS = 1e-6;
  7 
  8 inline int sgn(const double &x) {
  9     if(fabs(x) < EPS) return 0;
 10     return x > 0 ? 1 : -1;
 11 }
 12 
 13 struct Point {
 14     double x, y;
 15     int v, l;
 16 };
 17 
 18 inline bool Cross(Point &sp, Point &ep, Point &op) {
 19     return (sp.x - op.x) * (ep.y - op.y) - (ep.x - op.x) * (sp.y - op.y) >= 0;
 20 }
 21 
 22 inline double dist(Point &a, Point &b) {
 23     return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
 24 }
 25 
 26 inline bool cmp(const Point &a, const Point &b) {
 27     if(a.y == b.y) return a.x < b.x;
 28     return a.y < b.y;
 29 }
 30 
 31 const int MAXN = 20;
 32 int stk[MAXN];
 33 bool cut[MAXN], ans[MAXN];
 34 Point p[MAXN], a[MAXN];
 35 int n, top;
 36 double answood;
 37 
 38 double Graham_scan(int n) {
 39     sort(p, p + n, cmp);
 40     top = 1;
 41     stk[0] = 0; stk[1] = 1;
 42     for(int i = 2; i < n; ++i) {
 43         while(top && Cross(p[i], p[stk[top]], p[stk[top - 1]])) --top;
 44         stk[++top] = i;
 45     }
 46     int len = top;
 47     stk[++top] = n - 2;
 48     for(int i = n - 3; i >= 0; --i) {
 49         while(top != len && Cross(p[i], p[stk[top]], p[stk[top - 1]])) --top;
 50         stk[++top] = i;
 51     }
 52     double sum = 0;
 53     stk[++top] = stk[0];
 54     for(int i = 0; i < top; ++i)
 55         sum += dist(p[stk[i]], p[stk[i+1]]);
 56     return sum;
 57 }
 58 
 59 int minval, mincut, sumval, sumlen;
 60 double uselen;
 61 
 62 void setans(int cutcnt) {
 63     for(int i = 1; i <= n; ++i) ans[i] = cut[i];
 64     minval = sumval;
 65     mincut = cutcnt;
 66     answood = sumlen - uselen;
 67 }
 68 
 69 void dfs(int dep, int cutcnt) {
 70     if(dep == n + 1) {
 71         if(n == cutcnt) return ;
 72         sumval = sumlen = 0;
 73         for(int i = 1; i <= n; ++i) {
 74             if(!cut[i]) continue;
 75             sumval += a[i].v;
 76             sumlen += a[i].l;
 77         }
 78         if(sumval > minval) return ;
 79         if(sumval == minval && cutcnt >= mincut) return ;
 80         if(n - cutcnt == 1) {
 81             uselen = 0;
 82             setans(cutcnt);
 83         }
 84         else if(n - cutcnt == 2) {
 85             int i1 = 0, i2 = 0;
 86             for(int i = 1; i <= n; ++i) {
 87                 if(cut[i]) continue;
 88                 if(!i1) i1 = i;
 89                 else i2 = i;
 90             }
 91             uselen = 2 * dist(a[i1], a[i2]);
 92             if(uselen <= sumlen) setans(cutcnt);
 93         }
 94         else {
 95             int pcnt = 0;
 96             for(int i = 1; i <= n; ++i) {
 97                 if(cut[i]) continue;
 98                 p[pcnt++] = a[i];
 99             }
100             uselen = Graham_scan(pcnt);
101             if(sgn(uselen - sumlen) <= 0) setans(cutcnt);
102         }
103         return ;
104     }
105     cut[dep] = false;
106     dfs(dep + 1, cutcnt);
107     cut[dep] = true;
108     dfs(dep + 1, cutcnt + 1);
109 }
110 
111 int main() {
112     int ca = 1;
113     while(scanf("%d", &n) != EOF && n) {
114         for(int i = 1; i <= n; ++i) {
115             scanf("%lf%lf%d%d", &a[i].x, &a[i].y, &a[i].v, &a[i].l);
116         }
117         mincut = MAXN;
118         minval = 0x7fffffff;
119         dfs(1, 0);
120         if(ca != 1) printf("
");
121         printf("Forest %d
", ca++);
122         printf("Cut these trees:");
123         for(int i = 1; i <= n; ++i) if(ans[i]) printf(" %d", i);
124         printf("
Extra wood: %.2f
", answood);
125     }
126 }

By 区彦开