首页 > ACM题库 > HDU-杭电 > hdu 1966 Minimax Triangulation-计算几何-[解题报告]C++
2013
12-26

hdu 1966 Minimax Triangulation-计算几何-[解题报告]C++

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

题目大意:给你n个点围城的多边形,顺时针或者逆时针给你,起始点任意,让你把他划成n-2个三角形,这些划法中最大的三角形的面积最小,输出这个最小值。

思路:按照区间长度进行DP。对于 i~j 这些点,考虑新加入的点是j,那么就多了两条弦 i~j,j-1 ~j,对于 i~j 这条弦,加进去,它能围成的是 tran(i,k,j),i<k<j,,此时最大的三角形是 max( tran( i , k , j ) ,d[ i ][ k ] ,d[ k ][ j ] ),d[ i ][ j ] 表示按照题目给的方向来的 i ~ j 的最小的面积,对于这些又取最小,就是d[ i ][ j ] = min(max( tran( i , k , j ) ,d[ i ][
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) 的时候,它有可能是凹多边形,要判断有没有出界,这个时候只要枚举除这三个点的全部的点,用面积和看看他们中间有没有点就行了。

自己想的时候,状态方程的有一步转移不会写,我 i~j 的写好了,然后是 j – 1~j 的了,可i 和j 并不是相邻的,没法用之前的 d 转移,看了别人的之后才发现原来不用了。。。 还有判断是否出界这个问题,我想的竟然是先判断是顺时针或逆时针,然后直接根据这个方向判断是否出界,一直WA,脑子抽了,用方向是能判断,也要跑一下所有点啊,三个点,又要判断方向,这样挺麻烦的,后来又看了下别人的,发现他们都是直接用面积和来判断的,这样比较方便的。。 = =

代码如下:

#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;
    void read()
    {
        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++)
        {
            p[i].read();
        }
        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

*/

解题转自:http://blog.csdn.net/zstu_zlj/article/details/12220261


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

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