题解：P3744 李彬的几何

· · 题解

主要思路

其实这个题思路没有那么复杂

为使 P 凸性消失，最优情形为平移至三点共线。

考虑对于给定的 3 个顶点 P_i,P_j,P_k，求最小距离 D。

容易猜测结论：所求最小距离即为 \frac{1}{2}\times\triangle P_iP_jP_k 的最短高的长度。

简证：如图所示：(画质感人)

分别以 P_i,P_j,P_k 为圆心，最短高长度的 \frac{1}{2} 为半径作圆。不妨设 P_jP_k 为最长边，由定义 \triangle P_iP_jP_k 平行于 P_jP_k 的中位线为三圆公切线。

若存在直线 l，P_i,P_j,P_k到 l 的距离均小于半径长，则直线 l 与圆 P_i,P_j,P_k 均相交。而与圆 P_j,P_k 均相交的直线位于上图中（由圆 P_j,P_k 的内外公切线围成的）橙色区域，易知与圆 P_i 交集为空，矛盾！

回到原题，由于高即为顶点到底边的距离，我们只需枚举所有点对 (P_i,P_j)，计算其余点到 P_iP_j 的距离最小值，求出所有距离最小值的最小值即可。时间复杂度 O(n^3)？

（显然的）优化：由于其余点到 P_iP_j 的距离取到最小值时，必为 P_i 或 P_j 的邻点。只需对每对点对枚举至多 4 个点即可。复杂度 O(n^2)。

计算距离使用点到直线距离公式即可。

CODE

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct Point{
    ll x,y;
} p[1009];
double d(Point p1,Point p2,Point p3){
    return abs((p2.x-p3.x)*p1.y-(p2.y-p3.y)*p1.x+p2.y*p3.x-p2.x*p3.y)/sqrt(pow(p2.x-p3.x,2)+pow(p2.y-p3.y,2));
}
ll n,pre[1009],nxt[1009];
double mn=1000000000.0;
int main(){
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>p[i].x>>p[i].y;
        pre[i]=((i==1)?n:i-1),nxt[i]=((i==n)?1:i+1);
    }
    for(ll i=1;i<=n;i++){
        for(ll j=1;j<=n;j++){
            if(j==i) continue;
            if(pre[i]!=j) mn=min(mn,d(p[pre[i]],p[i],p[j]));
            if(nxt[i]!=j) mn=min(mn,d(p[nxt[i]],p[i],p[j]));
            if(pre[j]!=i) mn=min(mn,d(p[pre[j]],p[i],p[j]));
            if(nxt[j]!=i) mn=min(mn,d(p[nxt[j]],p[i],p[j]));
        }
    }
    cout<<mn/2.0<<endl;
    return 0;
}

求通过qwq