## Algorithm

Problem Name: 2 AD-HOC - beecrowd | 1717

# Cut

By Guilherme Albuquerque Pinto Brazil

Timelimit: 1

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 2N 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

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
#include <bits/stdc++.h>

using namespace std;

int n;
vector < pair > 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';
}
}
``````
Copy The Code &

Input

cmd
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

Output

cmd
4519.6176