题解：P3744 李彬的几何

fkjhzhkjv · 2026-04-23 21:08:02 · 题解

首先对结论进行大胆猜测：本题可以枚举每三个相邻点，计算出第二个点到第一、三个点的线段的距离，当距离最小时最优。

考虑证明：题目保证给出的是凸多边形，只需让一点移到与相邻两点共线时即可破坏该性质，而一个点向相邻两点移动时最短肯定是沿垂线方向移最短，那我们就只需证明枚举相邻三个点一定是最优情况就行了。
如下图：

若我们选择一、四号点来考虑二、三号点，则如下图：

很明显二和三到红线的距离是大于到黄线的距离的，我们很明显就能发现枚举相邻三个点是更优的。我使用的是向量叉乘求面积，不知道为什么会输出负数，需要加绝对值才能通过本题。

证明完成，我们就可以很容易的写出本题代码了：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
struct node{
    int x, y;
}ma[1007];
double cross(node x_from, node x_to, node y_from, node y_to){
    return (x_to.x - x_from.x) * (y_to.y - y_from.y) - (y_to.x - y_from.x) * (x_to.y - x_from.y);
}
double len(node x, node y){
    return sqrt((y.x - x.x) * (y.x - x.x) + (y.y - x.y) * (y.y - x.y));
}
signed main(){
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> ma[i].x >> ma[i].y;
    }
    ma[n + 1] = ma[1], ma[n + 2] = ma[2];
    double ans = 998244353;
    for(int i = 1;i <= n;++i){
        double S = cross(ma[i], ma[i + 2], ma[i], ma[i + 1]);
        double h = S / len(ma[i], ma[i + 2]);
        h /= 2;
        if(h - ans < 0.000001){
            ans = h;
        }
    }
    printf("%.10lf", fabs(ans));
    return 0;
}