题解 P6711 【[BalticOI 2005] Polygon】

· · 题解

Portal

首先先说一下NO SOLUTION的充分必要条件：给出的边的长度中，最长的那一条的长度 \geq 剩余所有边的长度之和。这是很显然的，因为三角形中两边之和必大于第三边，而任意多边形总可以形变成为一个三角形。

现在我们在判断无解后，就要尝试构造一组解。这里是我的构造方法：

  1. 将所有边按照长度从大到小排序，并记 dis_i 为排序后的结果，sum_i 为排序后的后缀和。

  2. 我们分别令 P_0=(x_0,y_0),\dots,P_n=(x_{n-1},y_{n-1}) 表示凸包上的点。并令第一个点为 (0,0)，第二个点为 (dis_1,0)。

  3. 接下来，尝试将第 2\sim(n-1) 条边加入凸包。当加入第 i 条边时，它一定处于以 P_{i-1} 为圆心，dis_i 为半径的圆上。我们把这条边看作该圆上的一个向量，则该向量的倾角一定满足如下限制：

其倾角必严格大于 \vec{v}=(x_{i-1}-x_{i-2},y_{i-1}-y_{i-2}) 的倾角，并小于 \vec{u}=(-x_{i-1},-y_{i-1}) 的倾角。

具体可以看下图为例：

我的构造方式是希望 P_i 到原点的距离尽量趋近于 sum_{i+1}+\Delta，其中 \Delta 是一极小量，是为了使凸包上所有的边不共线。在正常使用中，我们取 \Delta=10^{-6}\times(n-i-2)。

那么如何让这一距离尽量趋近于上述值呢？二分向量倾角即可。注意到上图中注明了“不含边界”，故左右边界都加上一个 \epsilon，我取了 10^{-10}。

直接按照上述算法即可通过。

代码：

#include<bits/stdc++.h>
using namespace std;
const double pi=acos(-1);
const double eps=1e-10;
const double rem=1e-6;
int n;
double dis[1010],sum[1010];
double x[1010],y[1010];
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%lf",&dis[i]);
    sort(dis+1,dis+n+1),reverse(dis+1,dis+n+1);
    for(int i=n;i;i--)sum[i]=dis[i]+sum[i+1];
    if(sum[2]<=dis[1]){puts("NO SOLUTION");return 0;}
    x[0]=y[0]=0,x[1]=dis[1],y[1]=0;
    for(int i=2;i<n;i++){
        double l=atan2(y[i-1]-y[i-2],x[i-1]-x[i-2])+eps,r=atan2(-y[i-1],-x[i-1])-eps;
        if(r<l)r+=2*pi;
//      printf("%lf %lf\n",l,r);
        while(r-l>eps){
            double mid=(l+r)/2;
            double nx=x[i-1]+cos(mid)*dis[i],ny=y[i-1]+sin(mid)*dis[i];
//          printf("%lf:%lf,%lf\n",mid,sqrt(nx*nx+ny*ny),(sum[i+1]+rem*(n-i-1)));
            if(sqrt(nx*nx+ny*ny)>=(sum[i+1]+rem*(n-i-2)))l=mid;
            else r=mid;
        }
        x[i]=x[i-1]+cos(l)*dis[i],y[i]=y[i-1]+sin(l)*dis[i];
    }
    for(int i=0;i<n;i++)printf("%.14lf %.14lf\n",x[i],y[i]);
//  for(int i=1;i<n;i++)printf("%.14lf\n",sqrt((x[i]-x[i-1])*(x[i]-x[i-1])+(y[i]-y[i-1])*(y[i]-y[i-1])));printf("%.14lf\n",sqrt(x[n-1]*x[n-1]+y[n-1]*y[n-1]));
    return 0;
}