2013
12-26

Minimax Triangulation

Triangulation of surfaces has applications in the Finite Element Method of solid mechanics. The objective is to estimate the stress and strain on complex objects by partitioning them into small simple objects which are considered incompressible. It is convenient to approximate a plane surface with a simple polygon, i.e., a piecewise-linear, closed curve in the plane on m distinct vertices, which does not intersect itself. A chord is a line segment between two non-adjacent vertices of the polygon which lies entirely inside the polygon, so in particular, the endpoints of the chord are the only points of the chord that touch the boundary of the polygon. A triangulation of the polygon, is any choice of m – 3 chords, such that the polygon is divided into triangles. In a triangulation, no two of the chosen chords intersect each other, except at endpoints, and all of the remaining (unchosen) chords cross at least one of the chosen chords. Fortunately, finding an arbitrary triangulation is a fairly easy task, but what if you were asked to find the best triangulation according to some measure?

Figure I.1: Five out of nine possible triangulations of the example polygon. The leftmost has
the smallest largest triangle.

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing one positive integer 2 < m < 50, being the number of vertices of the simple polygon. The following m lines contain the vertices of the polygon in the order they appear along the border, going either clockwise or counter clockwise, starting at an arbitrary vertex. Each vertex is described by a pair of integers x y obeying 0 <= x <= 10 000 and 0 <= y <= 10 000.

On the first line of the input is a single positive integer n, telling the number of test scenarios to follow. Each scenario begins with a line containing one positive integer 2 < m < 50, being the number of vertices of the simple polygon. The following m lines contain the vertices of the polygon in the order they appear along the border, going either clockwise or counter clockwise, starting at an arbitrary vertex. Each vertex is described by a pair of integers x y obeying 0 <= x <= 10 000 and 0 <= y <= 10 000.

1
6
7 0
6 2
9 5
3 5
0 3
1 1

9.0

k ] ，d[ k ][ j ] )，d[ i ][ j ]），i<k<j，而同时，j – 1~j它围成的已经在d[ k ][ j ] 之中包含了， 综合起来就是上面那个式子，长度从4开始DP，初始化为长度3的，为了统一，要把长度1、2的变成0,。这里还有一个关键的地方，那就是 tran( i , k , j) 的时候，它有可能是凹多边形，要判断有没有出界，这个时候只要枚举除这三个点的全部的点，用面积和看看他们中间有没有点就行了。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;

const double INF = 1e11;

const int MAXN = 55;

int n;

struct Point
{
int x,y;
{
scanf("%d%d",&x,&y);
}
} p[MAXN];

inline double Cross(Point &a, Point &b, Point &c) {                    // 叉积
return (b.x-a.x)*(c.y-a.y) - (c.x-a.x)*(b.y-a.y);
}

int check(int a,int b,int c)
{
int tt = fabs(Cross(p[a],p[b],p[c]));
for(int i = 0;i<n;i++)
{
if(i == a || i == b ||i == c) continue;
int tmp = fabs(Cross(p[a],p[b],p[i])) + fabs(Cross(p[a],p[c],p[i])) + fabs(Cross(p[b],p[c],p[i]));
if(tmp == tt) return 0;
}
return 1;
}

double d[MAXN][MAXN];

int main()
{
int _;
scanf("%d",&_);
while(_--)
{
scanf("%d",&n);
for(int i = 0;i<n;i++)
{
}
for(int len = 1;len<=2;len++)
for(int i = 0;i<n;i++)
d[i][(i+len-1)%n] = 0;
for(int i = 0;i<n;i++)
{
d[i][(i+2)%n] = fabs(Cross(p[i],p[(i+1)%n],p[(i+2)%n]))/2.0;
}
for(int len = 4;len<=n;len++)
{
for(int i = 0;i<n;i++)
{
int j = (i + len - 1)%n;
d[i][j] = INF;
for(int k = (i+1)%n; k!= j; k = (k+1)%n)
{
if(check(i,k,j)) d[i][j] = min(d[i][j],max(max(d[i][k],d[k][j]),fabs(Cross(p[i],p[k],p[j]))/2.0));
}
//printf("i = %d,j = %d,d = %f\n",i,j,d[i][j]);
}
}
double ans = INF;
for(int i = 0;i<n;i++)
ans = min(d[i][(i+n-1)%n],ans);
printf("%.1f\n",ans);
}
return 0;
}

/*

6
1 1
0 3
3 5
9 5
6 2
7 0

*/

1. 学算法中的数据结构学到一定程度会乐此不疲的，比如其中的2－3树，类似的红黑树，我甚至可以自己写个逻辑文件系统结构来。

2. 我还有个问题想请教一下，就是感觉对于新手来说，递归理解起来有些困难，不知有没有什么好的方法或者什么好的建议？