UVA 1331Minimax Triangulation——最优三角剖分

UVA 1331Minimax Triangulation——最优三角剖分

转移方程：dp[i][j] = min{dp[i][j], max{dp[i][k], dp[k][j], area(i, j, k)}}

这题坑在判断三角形是否在多边形内部，想想发现有些三角形虽然在多边形外部，但他们不会对结果造成影响，只有这样的三角形会对结果造成影响：三角形在多边形外部，且三角形内部有多边形的顶点。所以只需要判断点和三角形的关系就可以了。

不是很好想

#include #include #include #include #include using namespace std;const double INF = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 100;struct Point { double x, y; Point(double xx = 0, double yy = 0) : x(xx), y(yy) {}};typedef Point Vector;int n;double dp[maxn][maxn];Point p[maxn];Vector operator - (const Vector a, const Vector b) { return Vector(a.x-b.x, a.y-b.y); }int dcmp(double x) { if (fabs(x) < eps) return 0; if (x > 0) return 1; else return -1;}double Cross(Vector a, Vector b) { return a.x*b.y - b.x*a.y; }double area(int x, int y, int z) { return Cross(p[y] - p[x], p[z] - p[x]) / 2.0;}bool judge(int x, int y, int z) { for (int i = 1; i <= n; i++) { if (i == x || i == y || i == z) continue; double temp = area(i, x, y) + area(i, y, z) + area(i, z, x) - area(x, y, z); if (dcmp(temp) != 0) return false; } return true;}int main() { int T; scanf("%d", &T); for (int kase = 1; kase <= T; kase++) { scanf("%d", &n); for (int i = 1; i <= n; i++) scanf("%lf %lf", &p[i].x, &p[i].y); for (int i = 0; i <= n; i++) dp[i][i+1] = 0.0; for (int len = 2; len < n; len++) { for (int i = 1; i + len <= n; i++) { int j = i + len; dp[i][j] = INF; for (int k = i + 1; k < j; k++) { if (judge(i, k, j)) dp[i][j] = min(dp[i][j], max(fabs(area(i, k, j)), max(dp[i][k], dp[k][j]))); } } } printf("%.1lf\n", dp[1][n]); } return 0;}

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