题解 P3744 【李彬的几何】

· · 题解

这题这其实是一个几何问题

前置知识

你需要知道什么是凸多边形和凹多边形

你还需要知道求三角形面积的海伦公式：已知一个一般三角形的三边 a,b,c 然后令 p=(a+b+c)/2，则三角形的面积

s=\sqrt{p(p-a)(p-b)(p-c)}

海伦公式的证明：

设三角形的三边 a,b,c 的对角分别为 A,B,C 则根据余弦定理有

\cos(C) = \frac{a^2+b^2-c^2}{2ab}

从而有

\sin(C) = \sqrt{1-\cos^2(C)} = \frac{ \sqrt{-a^4 -b^4 -c^4 +2a^2b^2 +2b^2c^2 +2c^2a^2} }{2ab}

因此三角形的面积 S 为

&\; \; \; \; \; S_{triangel} \\ &= \frac{1}{2}ab \sin(C) \\ &= \frac{1}{4}\sqrt{-a^4 -b^4 -c^4 +2a^2b^2 +2b^2c^2 +2c^2a^2} \\ &= \frac{1}{4}\sqrt{(2ab)^2-(a^2+b^2-c^2)^2} \\ &= \frac{1}{4}\sqrt{(2ab+a^2+b^2-c^2)(2ab-a^2-b^2+c^2)} \\ &= \frac{1}{4}\sqrt{[(a+b)^2-c^2)][c^2-(a-b)^2]} \\ &= \frac{1}{4}\sqrt{(a+b+c)(a+b-c)(a-b+c)(-a+b+c)} \\ &= \frac{1}{4}\sqrt{2p(2p-2a)(2p-2b)(2p-2c)} \\ &= \sqrt\frac{1}{16}\sqrt{16p(p-a)(p-b)(p-c)} \\ &= \sqrt{p(p-a)(p-b)(p-c)} \end{aligned}

其中 p=(a+b+c)/2

最后你要知道勾股定理（这个应该没人不知道吧）

给你一个直角三角形，以及直角三角形的两条直角边 a,b 和斜边 c 则 a,b,c 一定满足

a^2+b^2=c^2

解题思路

我们不难想到，让一个凸多边形变成不是凸多边形，其实就是让一个凸多边形变成凹四边形，具体怎么转换呢？我们不妨看一张图

可以看出，让凸四边形变成凹四边形的方法就是把其中一个顶点的旁边两个点固定，然后把这个顶点移动一定的距离，而题目让我们求的距离就是这个顶点移动的距离的最小值 d，怎么求呢？

想要让 d 最小，其实只要在每一个顶点都求一次移动这个顶点所需最小的 d ，然后把各个 d 中间最小的取出来就是答案，现在我们就只需要思考怎么求移动一个顶点的 d 即可。

不妨设我们要移动的顶点是 A，发现想要 d 最小其实只需要把凸多边形变成一个 ∠A 刚好等于180°的内角即可，我们还知道，直线外一点到直线的距离最小的是垂线段，于是又可以得到下面这张图的移动方式

此时图中的 d 就是移动 A 点时使凸多边形变成凹多边形所需移动的最小距离。

接下来我们看看怎么算 d

首先题目已经告诉了我们每个点的坐标，于是我们就可以用两点之间的距离公式

dis(A,B)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

(其中 x_1,y_1 是 A 的横纵坐标,x_2,y_2 是 B 的横纵坐标)

来计算边 AB,BE,AE 的长度

先来证明一下两点之间的距离公式，首先我们选择平面上的任意两个点 A(x_1,y_1) 和 B(x_2,y_2)

然后我们可以做几条辅助线，如下图

我们做出一个直角三角形，然后根据给定的坐标可以算出两条直角边的长度是|x_1-x_2| 和 |y_1-y_2|

然后我们要求的是红色边的长度，我们就可以使用勾股定理

dis(A,B)^2=|x_1-x_2|^2+|y_1-y_2|^2

进一步化简即可得到

dis(A,B)=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}

然后我们使用三角形的面积公式

S_{triangel}ABE=\frac{d\times BE}{2}

进一步变形我们得到

d=\frac{2S_{triangel}ABE}{BE}

我们令 p=(AB+BE+AE)/2 然后使用海伦公式可以得到

d=\frac{2\sqrt{p(p-AB)(p-BE)(p-AE)}}{BE}

而且题目说我们不仅仅只能移动一个点，可以移动多个，只要范围都在 d 以内，于是我们可以进一步得到更小的 d_{min} 如下图

我们可以看到，在最优的情况下，d_{min} 可以缩小到原来的一半，于是我们可以得到最终的答案

d=\frac{\sqrt{p(p-AB)(p-BE)(p-AE)}}{BE}

接下来的步骤就简单了，照着公式写代码即可，但还要注意一些细节，比如这题在算两点之间的距离 dis(A,B) 时有用到平方，会爆 int，所以要开 long long ，而且有小数要用 double （这个应该没人会错吧），这样写出来的代码就没问题了。

还有一些注释可以见代码。

Code

#include <bits/stdc++.h>
using namespace std;
template<class T>T Min(register T a,register T b){
    return a<b?a:b;
}
template<class T>T Max(register T a,register T b){
    return a>b?a:b;
}
template<class T>T Abs(register T a){
    return a>0?a:-a;
}
template<class T>void Swap(register T &a,register T &b){
    T t=a;
    a=b;
    b=t;
}
//更快的min,max,abs,swap
const long long N=100100;
long long X[N],Y[N];
double dis(long long x,long long y){
    return sqrtl((X[x]-X[y])*(X[x]-X[y])+(Y[x]-Y[y])*(Y[x]-Y[y]));//算平面上两个点的距离
}
double Dis(long long x,long long y,long long z){//算把Y点移动d距离变成凹多边形时d的最小值
    double dx=dis(x,y);
    double dy=dis(y,z);
    double dz=dis(z,x);
    double p=(dx+dy+dz)/2.0;//半周长p
    double s=sqrtl(p*(p-dx)*(p-dy)*(p-dz));
    return s*1.0/dz/**2.0*/;//由于题目说每个点都能移动d,所以可以进一步缩短一半,原来推出来的公式中的*2就和/2抵掉了,所以就不用*2了
}
int main(){
    long long n;
    scanf("%lld",&n);
    for(long long i=1;i<=n;i++){
        scanf("%lld%lld",&X[i],&Y[i]);
    }
    double ans=Min(Dis(n,1,2),Dis(n-1,n,1));
    for(long long i=2;i<=n-1;i++){
        ans=Min(ans,Dis(i-1,i,i+1));
    }
    printf("%.10lf\n",ans);
    return 0;
}

于是这题就做完了。

另外，安利一下蒟蒻的博客

求管理员大大通过qwq