专栏文章

题解：P3744 李彬的几何

PPJM2008
P3744题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miofchwt
此快照首次捕获于
2025/12/02 18:17
3 个月前
此快照最后确认于
2025/12/02 18:17
3 个月前
查看原文

主要思路

其实这个题思路没有那么复杂
为使 PP 凸性消失，最优情形为平移至三点共线。
考虑对于给定的 33 个顶点 Pi,Pj,PkP_i,P_j,P_k，求最小距离 DD。
容易猜测结论：所求最小距离即为 12×△PiPjPk\frac{1}{2}\times\triangle P_iP_jP_k 的最短高的长度。
简证：如图所示：(画质感人)
分别以 Pi,Pj,PkP_i,P_j,P_k 为圆心，最短高长度的 12\frac{1}{2} 为半径作圆。不妨设 PjPkP_jP_k 为最长边，由定义 △PiPjPk\triangle P_iP_jP_k 平行于 PjPkP_jP_k 的中位线为三圆公切线。
若存在直线 ll，Pi,Pj,PkP_i,P_j,P_k到 ll 的距离均小于半径长，则直线 ll 与圆 Pi,Pj,PkP_i,P_j,P_k 均相交。而与圆 Pj,PkP_j,P_k 均相交的直线位于上图中（由圆 Pj,PkP_j,P_k 的内外公切线围成的）橙色区域，易知与圆 PiP_i 交集为空，矛盾！
回到原题，由于高即为顶点到底边的距离，我们只需枚举所有点对 (Pi,Pj)(P_i,P_j)，计算其余点到 PiPjP_iP_j 的距离最小值，求出所有距离最小值的最小值即可。时间复杂度 O(n3)O(n^3)？
（显然的）优化：由于其余点到 PiPjP_iP_j 的距离取到最小值时，必为 PiP_i 或 PjP_j 的邻点。只需对每对点对枚举至多 44 个点即可。复杂度 O(n2)O(n^2)。
计算距离使用点到直线距离公式即可。

CODE

CPP
#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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...