例题 P1452 [USACO03FALL] Beauty Contest G
P1452 [USACO03FALL] Beauty Contest G
题目描述
给定平面上 \(n\) 个点，求凸包直径。
输入格式
第一行一个正整数 \(n\)。
接下来 \(n\) 行，每行两个整数 \(x,y\)，表示一个点的坐标。保证所有点的坐标两两不同。
输出格式
输出一行一个整数，表示答案的平方。
输入输出样例 #1
输入 #1
4
0 0
0 1
1 1
1 0输出 #1
2
说明/提示
数据范围
对于 \(100\%\) 的数据，\(2\le n\le 5\times 10^4\)，\(|x|,|y|\le 10^4\)。
\(\text{upd 2022.7.22}\)：新增加四组 Hack 数据。
思路
在求完逆时针排序的凸包后，直接逆时针双指针不断更新最大距离就行了。这里重点讲距离怎么求。
叉积可以算出向量 \(\vec a=(x_1,y_1)\) 和 \(\vec b=(x_2,y_2)\) 所围成的平行四边形的面积（有正负），下面推其公式。
设
\[\begin{cases}
x_1=r_1\cos\alpha\\
y_1=r_1\sin\alpha
\end{cases},
\begin{cases}
x_2=r_2\cos\beta\\
y_2=r_2\sin\beta
\end{cases}
\]
，则由几何关系，\(\vec a\times \vec b=r_1\cdot r_2\cdot\sin(\beta-\alpha)\) ，注意由于叉积是 \(\vec a\) 逆时针（逆时针是由于右手螺旋）转到 \(\vec b\) ，所以是 \(\beta-\alpha\) 。
简单拆一下式子，发现
\[\begin{aligned}
\vec a\times \vec b&=r_1\cdot r_2\cdot\sin(\beta-\alpha)\\&=r_1\cdot r_2\cdot(\sin\beta\cos\alpha-\cos\beta\sin\alpha)\\
&=x_1y_2-y_1x_2
\end{aligned}
\]
就这样了。