P3744 李彬的几何 题解
ARIS0_0
·
·
题解
1. 题意解释
给出一个凸多边形各点的坐标，求移动若干个点使此凸多边形变成非凸多边形的最小移动距离。
2. 思路
这是一道很水的数学题。
我们知道，在凸多边形中，每个顶点与另外两个顶点相连（显然，不知道的重学初等几何）。
而根据凸多边形的定义，这三点显然是不共线的。
所以假如我们让这三点共线，这个多边形即不再是凸多边形。
为方便，我们记两边的两点分别为 A 和 B，记与 A 和 B 都相连的点为 C。
我们的目标也就是把 C 移动到线段 AB 上。
容易知道，我们过 C 作 AB 的垂线 CH 与 AB 相交与点 H，则 CH 是移动的最小距离。
海伦公式、秦九韶公式、割补法、行列式法随你选，爱用哪个用哪个。
求出 $CH$ 后，仍然不是最终的答案。
由于我们可以不止移动一个点，我们可以让 $AB$ 整体向上移动 $\dfrac{CH}{2}$ 的距离，$C$ 点也移动 $\dfrac{CH}{2}$ 的距离，则 $C$ 点仍落在 $AB$ 上。
因此最终答案为 $\dfrac{CH}{2}$ 的最小值。
由于题目保证点按照顺时针顺序给出，因此处理并不难，在此不多赘述。
### 3. 代码实现
记得多开几个 double。
```cpp
#include<bits/stdc++.h>
using namespace std;
int n;
struct data{
double x,y;
}a[1010];
double ans=1e9;
double calc(int p,int q,int j){
return abs(a[p].x*a[q].y+a[q].x*a[j].y+a[j].x*a[p].y-a[p].x*a[j].y-a[q].x*a[p].y-a[j].x*a[q].y)/2;
}
double dist(int p,int q){
return sqrt((a[p].x-a[q].x)*(a[p].x-a[q].x)+(a[p].y-a[q].y)*(a[p].y-a[q].y));
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i].x>>a[i].y;
}
a[n+1].x=a[1].x,a[n+1].y=a[1].y;
a[0].x=a[n].x,a[0].y=a[n].y;
for(int i=1;i<=n;i++){
double S=calc(i-1,i,i+1);
double l=dist(i-1,i+1);
double d=S/l;
ans=min(ans,d);
}
cout<<ans;
return 0;
}
```