3762专题

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

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3762 思路:(转自这篇文章) 先讨论锐角/直角三角形的情况: 假设拥有最大高的三角形是ABC,如下图结合此图我们可以看出最大高是点C到直线AB,在这种情况下,下列两个结论至少有一个成立1.点C是所有点中距离点A最远的2.点C是所有点中距离点B最远的反证: