RT,交在 vjudge 上显示 PE 了,但感觉输出格式没错啊???
#include <algorithm>
#include <cmath>
#include <iostream>
#include <vector>
using namespace std;
#define double long double
#define LL long long;
const int kMaxN = 16;
double x[kMaxN], y[kMaxN], v[kMaxN], l[kMaxN], q[kMaxN], px, ans;
int vis[kMaxN], id[kMaxN], n;
vector<int> t;
double M(int a, int b, int c) {
return (x[b] - x[a]) * (y[c] - y[a]) - (x[c] - x[a]) * (y[b] - y[a]);
}
double D(int l, int r) {
return sqrt((x[r] - x[l]) * (x[r] - x[l]) + (y[r] - y[l]) * (y[r] - y[l]));
}
bool C(int x, int y) {
double v = M(0, x, y);
return v > 0 || !v && D(x, 0) < D(y, 0);
}
void D(int s, double sum, double len) {
if (s > n) {
int cnt = 0, r = 0;
double lx = 0;
x[0] = y[0] = 1e9;
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
id[++cnt] = i;
if (x[i] < x[0]) {
x[0] = x[i], y[0] = y[i];
} else if (x[i] == x[0]) {
y[0] = min(y[0], y[i]);
}
}
}
sort(id + 1, id + cnt + 1, C);
for (int i = 1; i <= cnt; i++) {
for (; r > 1 && M(q[r - 1], q[r], id[i]) <= 0; r--) {
}
q[++r] = id[i];
}
for (int i = 1; i < r; i++) {
lx += D(q[i], q[i + 1]);
}
lx += D(q[1], q[r]);
if (lx <= len) {
if (sum > ans) {
ans = sum;
t.clear();
px = 0;
for (int i = 1; i <= n; i++) {
if (vis[i]) {
t.push_back(i);
}
}
px = len - lx;
}
}
return;
}
D(s + 1, sum + v[s], len);
vis[s] = 1;
D(s + 1, sum, len + l[s]);
vis[s] = 0;
}
void I() {
t.clear();
for (int i = 1; i <= n; i++) {
x[i] = y[i] = v[i] = l[i] = q[i] = vis[i] = id[i] = 0;
}
px = ans = 0;
}
int main() {
// freopen(".out", "w", stdout);
int c = 0;
while (cin >> n) {
if (!n) {
return 0;
}
if (c) {
cout << "\n";
}
c++;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> y[i] >> v[i] >> l[i];
}
D(1, 0, 0);
cout << "Forest " << c << "\n";
cout << "Cut these trees:";
for (int i = 0; i < t.size(); i++) {
cout << " " << t[i];
}
cout << "\n";
cout << "Extra wood: ";
printf("%.2Lf", px);
I();
}
return 0;
}