Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1717
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/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';
}
}
Input
Output