[UVA][凸包、窮舉] 811 - The Fortified Forest
The Fortified Forest
| The Fortified Forest |
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.
Input
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
n15, the number of trees in the forest.
The trees are identified by consecutive integers
1 to n. Each of the subsequent 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).
Output
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 a 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.
Sample Input
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
Sample Output
Forest 1 Cut these trees: 2 4 5 Extra wood: 3.16 Forest 2 Cut these trees: 2 Extra wood: 15.00
Miguel Revilla 2002-06-25
簡單說明一下題目：
國王想要築起圍欄保護樹木，然而必須砍掉其中幾棵樹做為圍欄，而剩餘的樹木周圍就用被砍掉的樹木做圍欄，國王希望用最少價值(每個樹木各自有價值與高度)保護最多的樹木。
窮舉砍與不砍的情況 O(2^n), 不砍的樹建立凸包, 並且計算其周長,
記住只有兩棵樹的時候, 周長是距離的兩倍,
國王不會把任何一個樹木交給徒匪, 因此會有多餘的樹木長度,
花費的價值越少越好, 砍的數目越少越好。
#include <stdio.h>
#include <math.h>
#include <algorithm>
using namespace std;
struct Pt {
double x, y;
bool operator<(const Pt &a) const {
if(x != a.x)
return x < a.x;
return y < a.y;
}
};
#define eps 1e-8
double cross(Pt o, Pt a, Pt b) {
return (a.x-o.x)*(b.y-o.y)-(a.y-o.y)*(b.x-o.x);
}
double dist(Pt a, Pt b) {
return sqrt(pow(a.x-b.x,2)+pow(a.y-b.y,2));
}
double calcConvexBounds(Pt p[], int n) {
if(n == 1) return 0;
sort(p, p+n);
Pt ch[20];
int i, m = 0, t;
for(i = 0; i < n; i++) {
while(m >= 2 && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
for(i = n-1, t = m+1; i >= 0; i--) {
while(m >= t && cross(ch[m-2], ch[m-1], p[i]) <= 0)
m--;
ch[m++] = p[i];
}
m--;
if(m == 2)
return 2*dist(ch[0], ch[1]);
double bounds = 0;
for(i = 0, t = m-1; i < m; t = i++)
bounds += dist(ch[i], ch[t]);
return bounds;
}
int main() {
int n, m;
int i, j, k;
int cases = 0;
double x[20], y[20], v[20], l[20];
Pt tree[20];
while(scanf("%d", &n) == 1 && n) {
if(cases) puts("");
for(i = 0; i < n; i++)
scanf("%lf %lf %lf %lf", &x[i], &y[i], &v[i], &l[i]);
double mncost = 0xffffff, extrawood;
int mnstate, mncut;
for(i = (1<<n)-1; i > 0; i--) { // cut state
double bounds = 0, cost = 0;
int cut = 0;
m = 0;
for(j = 0; j < n; j++) {
if((i>>j)&1) {
bounds += l[j];
cost += v[j];
cut++;
} else {
tree[m].x = x[j];
tree[m].y = y[j];
m++;
}
}
if(cost > mncost) continue;
double needBound = calcConvexBounds(tree, m);
//printf("%d %lf %lf %lf %lf\n", i, cost, bounds-needBound, bounds, needBound);
if(needBound <= bounds+eps) {
if(mncost > cost || (fabs(mncost-cost) < eps && mncut > cut)) {
mncost = cost;
mncut = cut;
mnstate = i;
extrawood = bounds - needBound;
}
}
}
printf("Forest %d\n", ++cases);
printf("Cut these trees:");
for(i = 0; i < n; i++)
if((mnstate>>i)&1) printf(" %d", i+1);
puts("");
printf("Extra wood: %.2lf\n", extrawood);
}
return 0;
}