ZOJ 3762 Pan's Labyrinth (点集中的最大点-线距技巧性枚举)

本文主要是介绍ZOJ 3762 Pan's Labyrinth (点集中的最大点-线距技巧性枚举)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3762

思路：（转自这篇文章）

先讨论锐角/直角三角形的情况：

假设拥有最大高的三角形是ABC，如下图

结合此图我们可以看出最大高是点C到直线AB，在这种情况下，下列两个结论至少有一个成立
1.点C是所有点中距离点A最远的
2.点C是所有点中距离点B最远的

反证：（这里先证明在AB上侧成立的情况）
首先过点C做直线A'B'平行于AB，再分别以点A、点B为圆心，AC、BC长为半径做圆
假设点C对上述两条结论均不成立，则还有一异于点C的点D至少满足上述两条结论之一，那么点D只能在直线A'B'以上且在圆A、B外的区域内。

显然，点D到直线AB的距离>点C到直线的距离，即△DAB的最大高>△CAB的最大高，与前提“拥有最大高的三角形是ABC”矛盾。
得证。
而在AB下侧，那两个圆的交点和点C是关于AB对称的，道理也一样，就不赘述了。
所以在△ABC是锐角/直角三角形时，“找最远点”的策略一定是对的。
再看看钝角三角形的情况：
这种情况发生在当点D位于点C的右下方，且在两个圆外面时。
这时△ACD的最大高>△ACB的最大高（可以画画辅助线对比下）
所以在△ABC是钝角三角形时，“找最远点”的策略亦是对的。
因此我们可以对每个点，先O(n)枚举距离它最远的点，再O(n)枚举三角形的另一个点就可以了，整体复杂度为O(n^2)。

完整代码：
/*510ms,176KB*/#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;struct P
{double x, y;
} p[505];///求pp到直线ab的距离
double dis(P &a, P &b, P &pp)
{if (b.x != a.x){double k = (b.y - a.y) / (b.x - a.x); ///直线斜率return fabs((pp.y - a.y) - k * (pp.x - a.x)) / sqrt(1 + k * k); ///套公式}return fabs(pp.x - a.x);
}int main()
{int n, i, j, maxp;double maxdis, tmp, ans;while (~scanf("%d", &n)){ans = 0;for (i = 0; i < n; i++) scanf("%lf%lf", &p[i].x, &p[i].y);for (i = 0; i < n; i++){maxdis = 0;for (j = 0; j < n; j++){if (i == j) continue;tmp = hypot(p[i].x - p[j].x, p[i].y - p[j].y);if (tmp > maxdis) maxdis = tmp, maxp = j;}for (j = 0; j < n; j++){if (j == i || j == maxp) continue;ans = max(dis(p[i], p[j], p[maxp]), ans);//ans = max(dis(p[i], p[maxp], p[j]), ans); ///由于i-pmax这条边一定不是最短边，故垂足一定不在这条直线上ans = max(dis(p[maxp], p[j], p[i]), ans); /// 最大高}}printf("%f\n", ans);}return 0;
}