UVA - 1543 Telescope（简单几何+区间DP）

题目链接

---

几何部分

已知圆的半径为1，我们看如何求出圆上两点距离：

首先$\angle AOB$已经确定，为$\theta =2\pi \ast (\alpha -\beta )$，那么我们可以求出$△AOB$的面积$S=\frac{r^2\ast sin\theta }{2}=r^2\ast sin\frac{\theta }{2}\ast cos\frac{\theta }{2}$，设$|AB|=x$，从$O$点作$AB$的垂线

那么在两个小三角形中，有$s=\frac{\frac{x}{2}\ast r\ast sin\frac{(\pi -\theta )}{2}}{2}=\frac{\frac{x}{2}\ast r\ast cos\frac{\theta }{2}}{2}$

因此有$S=2\ast s=\frac{x}{2}\ast r\ast cos\frac{\theta }{2}=r^2\ast sin\frac{\theta }{2}\ast cos\frac{\theta }{2}$

那么可以得到$x=2\ast r\ast sin\frac{\theta }{2}$，代入$r=1$，最终$x=2\ast sin\frac{\theta }{2},\theta =2\pi \ast (\alpha -\beta )$

DP部分

得到了任意两点之间的距离，那么我们可以用海伦公式求三角形的面积，在已经构造一个多边形后，我们发现如果再添加一个点之后，新增的面积就是一个原多边形起点和终点和新增点构成的三角形的面积

然后我们发现虽然这是一个圆，但是我们只需考虑一个线性的点序列，即环形的三角形已经在线性的三角形构造了。那么不难发现这就是一个区间DP的问题

设$d[i][j][k]$表示当前构造的多边形起点为$i$，终点为$j$，该多边形有$k$个顶点。那么有：

$d[i][k][len]=max(d[i][k][len],d[i][j][len-1]+getArea(i,j,k)),S△(i,j,k)=getArea(i,j,k)$

边界为初始化为$0$，最终的答案为$d[i][j][m]$

#include <set> #include <map> #include <stack> #include <queue> #include <math.h> #include <cstdio> #include <string> #include <bitset> #include <cstring> #include <sstream> #include <iostream> #include <algorithm> #include <unordered_map> using namespace std; #define fi first #define se second #define pb push_back #define ins insert #define lowbit(x) (x&(-x)) #define mkp(x,y) make_pair(x,y) #define mem(a,x) memset(a,x,sizeof a); typedef long long ll; typedef long double ld; typedef unsigned long long ull; typedef pair<int,int> P; const double eps=1e-8; const double pi=acos(-1.0); const int inf=0x3f3f3f3f; const ll INF=1e18; const int Mod=1e9+7; const int maxn=55; double a[maxn],p[maxn][maxn]; double d[maxn][maxn][maxn]; double dis(double x,double y){ return 2.0*sin(pi*(y-x)); } double getArea(int x,int y,int z){ double a=p[x][y],b=p[y][z],c=p[x][z]; double p=(a+b+c)/2; return sqrt(p*(p-a)*(p-b)*(p-c)); } int main(){ //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); //ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); int n,m; while(~scanf("%d%d",&n,&m) && n){ for(int i=1;i<=n;i++) scanf("%lf",&a[i]); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){ p[i][j]=p[j][i]=dis(a[i],a[j]); //预处理任意两点之间的距离 } memset(d,0,sizeof d); for(int len=3;len<=m;len++) for(int i=1;i<=n;i++){ for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++) d[i][k][len]=max(d[i][k][len],d[i][j][len-1]+getArea(i,j,k)); } double ans=0.0; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) ans=max(ans,d[i][j][m]); printf("%.6f\n",ans); } return 0; }