手机网站域名解析怎么做,网页制作素材小图片,网站备案信息页面,网站建设定制公司推荐题意#xff1a;输入一个简单m#xff08;2m50)边形#xff0c;找到一个最大三角形最小的三角剖分#xff08;用不相交的对角线把一个多边形分成若干个三角形#xff09;。输出最大的三角形面积。 分析#xff1a;每条对角线都是无序的#xff0c;因此#xff…题意输入一个简单m2m50)边形找到一个最大三角形最小的三角剖分用不相交的对角线把一个多边形分成若干个三角形。输出最大的三角形面积。 分析每条对角线都是无序的因此给节点编号从1到n-1顺时针方向这样多边形的顶点都是有序的了这样就可划分区间类似区间dp来做。 #includebits/stdc.h
using namespace std;const int maxn55;
const double inf0x3f3f3f3f;
const double eps1e-9;
double d[maxn][maxn];
int n;struct point
{double x,y;void get(){scanf(%lf%lf,x,y);}
}p[maxn];double area(point a,point b,point c)
{return fabs((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y))/2;
}bool judge(int a,int b,int c)
{double arearea(p[a],p[b],p[c]);for(int i0;in;i){if(ia||ib||ic)continue;double tmparea(p[a],p[b],p[i])area(p[a],p[c],p[i])area(p[b],p[c],p[i]);if(fabs(are-tmp)eps)return false;}return true;
}double solve()
{for(int i0;i2;i)for(int j0;jn;j)d[j][(ji)%n]0;for(int i0;in;i)d[i][(i2)%n]area(p[i],p[(i1)%n],p[(i2)%n]);for(int k3;kn;k){for(int i0;in;i){int en(ik)%n;d[i][en]inf;for(int j(i1)%n;j!en;j(j1)%n)if(judge(i,en,j))d[i][en]min(d[i][en],max(max(d[i][j],d[j][en]),area(p[i],p[j],p[en])));}}double ansinf;for(int i0;in;i)ansmin(ans,d[i][(in-1)%n]);return ans;
}int main()
{int t;cint;while(t--){cinn;for(int i0;in;i)p[i].get();printf(%.1lf\n,solve());}return 0;
} 转载于:https://www.cnblogs.com/mu-ye/p/5687139.html
