题解：P3744 李彬的几何

nyt_nyt2012 · 2026-05-11 22:05:38 · 题解

水蓝几何题，10 分钟切了。

显然，我们只需考虑每相邻三点的移动。我们将中间也就是最外侧的点往里挪，另外两点往外挪就能破坏凸多边形的凸的性质。所以我们只需枚举每组相邻三点，算出距离后求最小值即可。

考虑怎么计算距离。设这三点为 A,B,C，答案就是 B 到 AC 距离的一半。B 到 AC 距离可以用点到直线距离公式计算，但这需要用到 AC 的一般式，但这需要额外分讨 x_1=x_2 和 y_1=y_2 的情况，比较复杂。考虑使用面积法，求出 \Delta ABC 中 AC 边上的高然后除以 2，S_{\Delta ABC} 可以先用勾股定理求出边长再用海伦公式计算面积，然后计算高即可。唯一的问题就是误差，不过数据谁可以通过。

代码

#include<bits/stdc++.h>
#define double long double
using namespace std;
struct pm{
    int x,y;
}a[10010];
int n;
double sqr(double a){
    return a*a;
}
double mc(int o){
    double x2=a[o].x,y2=a[o].y,x1,y1,x3,y3,b1,b2,b3,q,s,g;
    if(o==1){
        x1=a[n].x;y1=a[n].y;
    }
    else{
        x1=a[o-1].x;y1=a[o-1].y;
    }
    if(o==n){
        x3=a[1].x;y3=a[1].y;
    }
    else{
        x3=a[o+1].x;y3=a[o+1].y;
    }
    b1=sqrt(sqr(abs(x2-x3))+sqr(abs(y2-y3)));
    b2=sqrt(sqr(abs(x1-x3))+sqr(abs(y1-y3)));
    b3=sqrt(sqr(abs(x2-x1))+sqr(abs(y2-y1)));
    q=(b1+b2+b3)/2;
    s=sqrt((q-b1)*(q-b2)*(q-b3)*q);
    g=s*2/b2;
    return g;
}
int main(){
    cin>>n;
    double ans=1e9+7;
    for(int i=1;i<=n;i++){
        cin>>a[i].x>>a[i].y;
    }
    for(int i=1;i<=n;i++){
        ans=min(ans,mc(i));
    }
    ans/=2;cout<<ans;
    return 0;
}