UVA 最大面积最小三角形剖分

flowchart 箭头图标 勿删

点击打开题目

题目大意：

以顺时针或逆时针给出一个简单多边形的n个点的坐标，用n-2条互不相交的，且与边不相交的对角线，分成n-2个三角形，要求其中最大三角形的面积最小

开始还汪星人咬乌龟，无从下口，但在度娘翻译的帮助下，看到了顺时针，眼前一亮，环形的分割问题

设f[i][j]表示从i号点到j号点这个子多边形的最大三角形面积最小值，则列出状态转移方程：

f[i][j]=min(f[i][j],max(S(i,j,k),max(f[i][k],f[k+1][j])));

不会算面积？海伦公式一波带走

设三角形三边为abc，设p=(a+b+c)/2

则S=(√p⋅(p−a)⋅(p−b)⋅(p−c))

美滋滋地码好代码交上去，WA了，我艹

猛然发现,(用n-2条互不相交的，且与 边不相交 的对角线)

23333333333333……

于是换个角度想想，如果一条对角线与边相交，那这条对角线形成的某个三角形，内部一定有点，于是我们可以枚举出这个点，如果某个点i，与三角形三点abc，形成：

S(a,b,i)+S(a,c,i)+S(b,c,i)=S(a,b,c)

那么这个点一定在三角形内，排除掉就行了

代码如下：

#include<cstdio>

#include<cmath>

#include<cstring>

#include<vector>

#include<algorithm>

#define INF 1<<30

#define eps 0.001

using namespace std;

double f[51][51];

double dis[51][51];

int n,x[51],y[51];

int getint()

{

    int num=0,flag=1;char c;

    while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;

    while(c>='0'&&c<='9')num=num*10+c-48,c=getchar();

    return num*flag;

}

double S(double a,double b,double c)

{

    double p=(a+b+c)/2;

    return sqrt(p*(p-a)*(p-b)*(p-c));

}

bool check(int a,int b,int c)

{

    for(int i=1;i<=n;i++)

        if(i!=a&&i!=b&&i!=c)

            if(fabs(S(dis[i][a],dis[i][b],dis[a][b])+S(dis[i][a],dis[i][c],dis[a][c])+S(dis[i][b],dis[i][c],dis[b][c])-S(dis[a][b],dis[a][c],dis[b][c]))<eps)

                return 1;

    return 0;

}

int main()

{

    int i,j,o,t=getint();

    while(t--)

    {

        memset(f,0x7f,sizeof f);

        n=getint();

        for(i=1;i<n;i++)f[i][i+1]=0;

        for(i=1;i<=n;i++)x[i]=getint(),y[i]=getint();

        for(i=1;i<=n;i++)for(j=1;j<=n;j++)dis[i][j]=sqrt(pow(x[i]-x[j],2)+pow(y[i]-y[j],2));

        for(o=2;o<=n;o++)

            for(i=1;i<=n-o;i++)

                for(j=i+1;j<i+o;j++)

                    if(!check(i,j,i+o))

                        f[i][i+o]=min(max(S(dis[i][j],dis[j][i+o],dis[i+o][i]),max(f[i][j],f[j][i+o])),f[i][i+o]);

        printf("%.1lf\n",f[1][n]);

    }

}