题意：砍掉一些树，用它们做成篱笆把剩余的树围起来，问最小价值
分析：数据量不大，考虑状态压缩暴力枚举，求凸包以及计算凸包长度。虽说是水题，毕竟是final，自己状压的最大情况写错了，而且忘记特判凸包点数 <= 1的情况。
/************************************************
* Author :Running_Time
* Created Time :2015/11/3 星期二 16:10:17
* File Name :POJ_1873.cpp
************************************************/ #include <cstdio>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#include <deque>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <bitset>
#include <cstdlib>
#include <ctime>
using namespace std; #define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
typedef long long ll;
const int N = 1e5 + 10;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = acos (-1.0);
int dcmp(double x) { //三态函数，减少精度问题
if (fabs (x) < EPS) return 0;
else return x < 0 ? -1 : 1;
}
struct Point { //点的定义
double x, y, v, l;
Point () {}
Point (double x, double y, double v, double l) : x (x), y (y), v (v), l (l) {}
Point operator + (const Point &r) const { //向量加法
return Point (x + r.x, y + r.y, 0, 0);
}
Point operator - (const Point &r) const { //向量减法
return Point (x - r.x, y - r.y, 0, 0);
}
Point operator * (double p) const { //向量乘以标量
return Point (x * p, y * p, 0, 0);
}
Point operator / (double p) const { //向量除以标量
return Point (x / p, y / p, 0, 0);
}
bool operator < (const Point &r) const { //点的坐标排序
return x < r.x || (x == r.x && y < r.y);
}
bool operator == (const Point &r) const { //判断同一个点
return dcmp (x - r.x) == 0 && dcmp (y - r.y) == 0;
}
};
typedef Point Vector; //向量的定义
Point read_point(void) { //点的读入
double x, y, v, l;
scanf ("%lf%lf%lf%lf", &x, &y, &v, &l);
return Point (x, y, v, l);
}
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 length(Vector A) { //向量长度，点积
return sqrt (dot (A, A));
}
Point qs[33], ps[33];
/*
点集凸包，输入点的集合，返回凸包点的集合。
如果不希望在凸包的边上有输入点，把两个 <= 改成 <
*/
int convex_hull(Point *ps, int n) {
sort (ps, ps+n); //x - y排序
int k = 0;
for (int i=0; i<n; ++i) {
while (k > 1 && cross (qs[k-1] - qs[k-2], ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
for (int i=n-2, t=k; i>=0; --i) {
while (k > t && cross (qs[k-1] - qs[k-2], ps[i] - qs[k-1]) <= 0) k--;
qs[k++] = ps[i];
}
return k-1;
} double cal_fence(Point *ps, int n) {
if (n <= 1) {
return 0;
}
n = convex_hull (ps, n);
double ret = 0;
for (int i=0; i<n-1; ++i) {
ret += length (qs[i+1] - qs[i]);
}
ret += length (qs[n-1] - qs[0]);
return ret;
} int main(void) {
int n, cas = 0;
while (scanf ("%d", &n) == 1) {
if (!n) break;
vector<Point> pps;
for (int i=0; i<n; ++i) {
pps.push_back (read_point ());
}
int S = 1 << n, sz = 100;
vector<int> ans, num;
int m = 0;
double sum = 0, val = 999999999, tval = 0, len = 0, ex = 0;
for (int i=0; i<S; ++i) {
num.clear (); tval = 0; sum = 0; m = 0;
for (int j=0; j<n; ++j) {
if (i & (1 << j)) { //cut
num.push_back (j + 1);
tval += pps[j].v; sum += pps[j].l;
}
else {
ps[m++] = pps[j];
}
}
len = cal_fence (ps, m);
if (sum < len) continue;
if (val > tval || (dcmp (val - tval) == 0 && sz > num.size ())) {
val = tval; sz = num.size ();
ans = num; ex = sum - len;
}
}
printf ("Forest %d\n", ++cas);
printf ("Cut these trees: ");
printf ("%d", ans[0]);
for (int i=1; i<ans.size (); ++i) {
printf (" %d", ans[i]);
}
puts ("");
printf ("Extra wood: %.2f\n\n", ex);
} //cout << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; return 0;
}