/** * Deon Nicholas' solution to InTents. * * The secret (besides fighting with volume formulas) * is that the problem can be solved greedily. * * -------------------------------------- * THE VOLUME FORMULA: * * First, assue we have already assigned all posts to locations. * * What is the volume of a single "triangle", assuming you place * posts with heights h1 and h2 respectively, and your origin post has height z? * * ==> (h1 + h2 + z) * (AREA / 3) * * Where AREA is the flat / birds-eye-view area of the triangle. (I derived * this by breaking the thing into a pair of smaller tetrahedra.) * * Summing over all the triangles, each h_i will be included in two * triangles (those that are incident to it). So a given h_i will contribute: * * (h_i*AREA_i1/3) + (h_i*AREA_i2/3) * * to the overall sum, where AREA_i1 and AREA_i2 are the areas of the triangles * that include that post. * * ==> h_i * (AREA_i1 + AREA_i2)/3 * -------------------------------------- * * -------------------------------------- * MAXIMIZING TOTAL VOLUME: * * Incidentally, the volume contributed by a single post of height h_i * is completely independent of the other posts. * * So, to maximize the volume, we simply need to place the posts in such a way * as to maximize: sum{h_i * (AREA_i1 + AREA_i2)/3} * * Using a Greedy Argument you can prove that you should *always* place the maximum * h_i with the maximum (AREA_i1 + AREA_i2)/3, and the second with the second, * etc, if you want to maximize the total sum (exercise?). * * So that's actually it. We sort the (AREA_i1 + AREA_i2) / 3, for all neighbouring * triangles, and sort the h_i, and add up the matching products. * * Oh, and since we don't know the origin post * right away, we just try all those. * * Overall run-time is O(N^2 log N) or O(N^2) if you're not lazy. * -------------------------------------- */ #include #include #include #include #include #include #include using namespace std; #define FOR(i,n) for(int i=0;i<(n);++i) #define MAXN 50 typedef long double ld; typedef pair pii; pii pts[MAXN]; // the points on the periphery int H[MAXN]; // height of post i ld area[MAXN]; // area of each triangle (birds-eye-view) ld sum_adj[MAXN]; // sum of adjacent areas: (area[i] + area[i+1]) / 3 ld tmp[MAXN]; // Solve greedily // Always match the tallest post with the point where it will contribute most // Contribution to volume is always sum_adj[i] * H[i] ld solve(int N, int P, int Z) { ld base = 0; FOR(i,P) base += Z*area[i]/3.0; FOR(i,N) tmp[i] = H[i]; sort(tmp,tmp+N); assert(N == P); FOR(i,N) base += tmp[i]*sum_adj[i]; return base; } ld theta(int x, int y) { return atan2(y,x); } ld theta(const pii& p) { return theta(p.first, p.second); } bool sort_by_angle(const pii& a, const pii& b) { return (a==b ? false : (theta(a) < theta(b))); } int main() { int N; scanf("%d", &N); int P = N-1; // P:= number of holes on periphal // input FOR(i,P) scanf("%d%d",&pts[i].first,&pts[i].second); FOR(i,N) scanf("%d",&H[i]); // sort points by angle around origin sort(pts, pts+P, sort_by_angle); // Compute the base areas of each triangle (birds-eye view) FOR(i,P) { int x1 = pts[i].first, h1 = pts[i].second; int x2 = pts[(i+1)%P].first, h2 = pts[(i+1)%P].second; // area of a triangle = 0.5 * [cross-product of it's two non-origin points] int cross = x1*h2 - h1*x2; area[i] = abs(cross / 2.0l); } // For each pair of adjacent triangles, sum their areas (divide by 3 to fit the formulas) FOR(i,P) sum_adj[i] = (area[i] + area[(i+1)%P]) / 3.0; sort(sum_adj,sum_adj+P); // Try all possible "origins", solve, take the best ld ans = 0; FOR(i,N) { swap(H[i], H[N-1]); ans = max(ans, solve(N-1, P, H[N-1])); swap(H[i], H[N-1]); } cout << fixed << setprecision(2) << ans << endl; }