UVA - 1543 Telescope——最优三角剖分

UVA - 1543 Telescope——最优三角剖分

最优三角剖分的变形

#include #include #include #include #include using namespace std;const double PI = acos(-1.0);const int maxn = 50;struct Point { double x, y; Point(double xx = 0, double yy = 0) : x(xx), y(yy) {}};typedef Point Vector;int n, m;double t, dp[maxn][maxn][maxn];Point p[maxn];Vector operator - (const Vector A, const Vector B) { return Vector(A.x-B.x, A.y-B.y); }double Cross(Vector A, Vector B) { return A.x*B.y-A.y*B.x; }double area(int x, int y, int z) { return fabs(Cross(p[y] - p[x], p[z] - p[x])) / 2.0;}Vector Rotate(Vector A, double rad) { return Vector(A.x*cos(rad)-A.y*sin(rad), A.x*sin(rad)+A.y*cos(rad));}int main() { Vector base; base.x = 1, base.y = 0; while (~scanf("%d %d", &n, &m) && (n + m)) { for (int i = 1; i <= n; i++) { scanf("%lf", &t); p[i] = Rotate(base, t * 2.0 * PI); } memset(dp, 0, sizeof(dp)); double ans = 0; for (int num = 3; num <= m; num++) { for (int len = 2; len < n; len++) { for (int i = 1; i + len <= n; i++) { int j = i + len; for (int k = i + 1; k < j; k++) { dp[num][i][j] = max(dp[num][i][j], max(dp[num-1][i][k], dp[num-1][k][j]) + area(i, k, j)); } ans = max(ans, dp[num][i][j]); } } } printf("%.6lf\n", ans); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。