三默网为您带来有关“凸多边形最优三角剖分”的文章内容,供您阅读参考。
凸多边形最优三角剖分
2023-01-21 17:17:53
一.问题描述
【问题描述】使用动态规划算法解凸多边形最优三角剖分问题,具体来说就是,依据递归式,按照顺序求得子问题,使得该三角剖分中诸三角形上权之和为最小。
【输入形式】在屏幕上输入凸多边形顶点个数和顶点坐标。
【输出形式】最优三角剖分后的三角形顶点。
【样例1输入】
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
【样例2输出】
012
234
024
456
046
二.思路
三.代码
#include<bits/stdc++.h>
using namespace std;
int t[50][50],s[50][50];
int arrx[50],arry[50];
int calweight(int a,int b,int c);
void MIN_WEIGHT_TRIANGULATION(int n){
int j;
for(int len=2;len<=n;len++){
for(int i=1;i<=n-len+1;i++){
j=i+len-1;
t[i][j]=0xFFFFFFF;
for(int k=i;k<=j-1;k++){
int q=t[i][k]+t[k+1][j]+calweight(i-1,k,j);
if(q<t[i][j]){
t[i][j]=q;
s[i][j]=k;
}
}
}
}
}
void print(int i,int j){
if(i==j)
return;
print(i,s[i][j]);
print(s[i][j]+1,j);
cout<<i-1<<s[i][j]<<j<<endl;
}
int calweight(int a,int b,int c){
int x=sqrt(pow(arrx[a]-arrx[b],2)+pow(arry[a]-arry[b],2));
int y=sqrt(pow(arrx[a]-arrx[c],2)+pow(arry[a]-arry[c],2));
int z=sqrt(pow(arrx[b]-arrx[c],2)+pow(arry[b]-arry[c],2));
return x+y+z;
}
int main(){
int cnt;
cin>>cnt;
for(int i=0;i<cnt;i++){
cin>>arrx[i]>>arry[i];
}
cnt--;
MIN_WEIGHT_TRIANGULATION(cnt);
print(1,cnt);
}
/*
7
8 26
0 20
0 10
10 0
22 12
27 21
15 26
*/