## [URI Online Judge] – 1717 – Cut

Link: https://www.urionlinejudge.com.br/judge/en/problems/view/1717

Every convex polygon, with 2N vertices, can be decomposed into N − 1 quadrilaterals, by making N − 2 straight line cuts between certain pairs of vertices. The figure below shows three different decompositions of the same polygon with N = 5. The weight of the decomposition is the sum of the lengths of its N −2 cuts. Your program should compute the weight of a minimum weight decomposition!

## Input

The input contains several test cases. The first line of a test case contains one integer **N** (2 ≤ **N** ≤ 100). The following **2N** lines contain, each one, two real numbers **X** and **Y** (0 ≤ **X**, **Y** ≤ 10000), with precision of 4 decimal digits: the coordinates of the 2**N** points, in counterclockwise order, of the convex polygon.

## Output

For each test case in the input your program must output one line containing a real number, with 4 decimal digits precision. The number should be the weight of a minimum weight decomposition of the given polygon.

Sample Input | Sample Output |

4 5715.7584 3278.6962 3870.5535 4086.7950 3823.2140 4080.7543 3574.4323 170.2905 4521.4796 144.9156 4984.6486 306.2896 5063.1061 347.1661 6099.9959 2095.9358 | 4519.6176 |

solution:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 | #include <bits/stdc++.h> using namespace std; int n; vector<pair<double, double> > v; double dp[206][206]; double d[206][206]; int usei[206][206]; double dist(int i, int j) { return hypot((v[i].first - v[j].first), (v[i].second - v[j].second)); } double calc(int v1, int v2) { if (v2 - v1 <= 3) return 0.00; double &ans = dp[v1][v2]; if (!usei[v1][v2]) { usei[v1][v2] = 1; double ret = 1e+30; for (int i = v1 + 1; i < v2; i += 2) { for (int j = i + 1; j < v2; j += 2) { ret = min(ret, calc(v1, i) + calc(i, j) + calc(j, v2) + d[v1][i] + d[i][j] + d[j][v2]); } } ans = ret; } return ans; } int main() { double x, y; cout.precision(4); while (cin >> n) { n *= 2; for (int i = 0 ; i < n ; ++i) { cin >> x >> y; v.push_back(make_pair(x, y)); } for (int i = 0 ; i < n; ++i) { for (int j = 0 ; j < n ; ++j) { d[i][j] = dist(i, j); dp[i][j] = -1.0; usei[i][j] = 0; } d[i][i + 1] = 0.0; } cout << fixed << calc(0, n - 1) << '\n'; } } |