UVA1543 圆和多边形 Telescope 题解

· · 题解

首先把多边形划分成同起点的多个三角形，那么我们显然可以动态规划，令 dp{i,j,k} 表示起点为 i 终点为 j 选了 k 个的最大值，那么转移方程为 dp_{i,nxt,k+1} = \max(dp_{i,nxt,k+1},dp_{i,j,k} + S)，其中 S 表示新加入的三角形面积，由起点 i，旧终点 j 和新终点 nxt 构成，接下来只要看怎么求解面积即可。

首先可以发现，给出的实数代表与周长的比值，可以转化为与 2\pi 之间的比值，这里使用弧度制，因为圆的半径为一，那么接下来转化为已知角的大小 \alpha，求在单位圆上对应的点的坐标，显然为 (\cos \alpha,\sin \alpha)，求解出三个点对应的坐标后利用海伦公式算出面积即可。

需要分别枚举起点 i，旧终点 j，新终点 nxt 和个数 k，时间复杂度量级为 O(n^4)。

#include<bits/stdc++.h>
using namespace std;
const double pi = acos(-1);
int n,m;
double p[45];
double dp[45][45][45];
double ans;
pair<double,double> trans(int i){//把第i个点转化为坐标形式
    double a = 2 * pi * p[i];
    return {cos(a),sin(a)};
}
double dis(double x1,double y1,double x2,double y2){//计算欧几里得距离
    return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}
double cal(int a,int b,int c){//海伦公式计算由三个点构成的三角形的面积
    pair<double,double> A = trans(a);
    pair<double,double> B = trans(b);
    pair<double,double> C = trans(c);
    double AB = dis(A.first,A.second,B.first,B.second);
    double BC = dis(B.first,B.second,C.first,C.second);
    double AC = dis(A.first,A.second,C.first,C.second);
    double p = (AB + BC + AC) / 2;
    return sqrt(p * (p - AB) * (p - BC) * (p - AC));
}
int main(){
    while(cin >> n >> m && (n || m)){
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=n;i++){
            cin >> p[i];
        }
        for(int i=1;i<=n-m+1;i++){
            for(int j=i+1;j<=n;j++){
                for(int k=2;k<m;k++){
                    for(int p=j+1;p<=n;p++){
                        dp[i][p][k + 1] = max(dp[i][p][k + 1],dp[i][j][k] + cal(i,j,p));
                    }
                }
            }
        }
        ans = 0;
        for(int i=1;i<=n-m+1;i++){
            for(int j=i+1;j<=n;j++){
                ans = max(ans,dp[i][j][m]);
            }
        }
        cout << fixed << setprecision(6) << ans << "\n";
    }
    return 0;
}