BYR Achieve · 镜像论坛

☆─────────────────────────────────────☆ chopin19 (肖邦在世||不懂算法) 于 (Tue Feb 3 17:25:47 2009) 提到: 求凸多边形的最远点对（就是距离最远的两个顶点），要求o(n)，n为顶点数 ☆─────────────────────────────────────☆ ox (小贝|抱抱三人组之小宝贝|东北志责任编辑) 于 (Tue Feb 3 18:01:28 2009) 提到: 数学问题，网上有不少关于这个问题的论文你可以下一个看看搜求凸多边形直径【在 chopin19 (肖邦在世||不懂算法) 的大作中提到: 】 : 求凸多边形的最远点对（就是距离最远的两个顶点），要求o(n)，n为顶点数 ☆─────────────────────────────────────☆ flyingmiao (amiao) 于 (Tue Feb 3 18:05:04 2009) 提到: 当年试图ACM时被虐过的题。。。 ☆─────────────────────────────────────☆ chopin19 (肖邦在世||不懂算法) 于 (Tue Feb 3 20:11:50 2009) 提到: 嗯，我说怎么搜最远点对出不来呢。大概明白了，求跖点对o（n）加上求跖点对中距离最长的o(n),合起来是o（n）：）【在 ox 的大作中提到: 】 : 数学问题，网上有不少关于这个问题的论文 : 你可以下一个看看 : 搜求凸多边形直径 ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Feb 4 03:00:13 2009) 提到: 两个点A,B：A初始化成任意一个点；B先走到A的对侧（离A最远的点）记录A-B距离然后A和B齐步走：A走一步，B试试走一步能不能比不走距离A更远。然后记录新的A-B距离。如此重复，直到A走完一圈。然后找到最大距离就可以了。时间复杂度：因为A走一圈,B不会超过两圈，所以复杂度是O(n) ☆─────────────────────────────────────☆ chopin19 (肖邦在世||不懂算法) 于 (Wed Feb 4 11:43:48 2009) 提到: 【在 wks 的大作中提到: 】 : 两个点A,B：A初始化成任意一个点；B先走到A的对侧（离A最远的点）记录A-B距离 : 然后A和B齐步走：A走一步，B试试走一步能不能比不走距离A更远。然后记录新的A-B距离。 //在这个地方，如何验证这个算法的正确性呢？ : 如此重复，直到A走完一圈。然后找到最大距离就可以了。 : ................... ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Feb 4 13:36:09 2009) 提到: 哦，算法错了。一开始，A走到y值最小的点，B走到y值最大的点。记录AB距离 A走到A'，B不是走到离点A'最远的地方，而是走到离直线AA'最远的地方。记录A'B'距离证明嘛，“旋转卡尺”法 http://cgm.cs.mcgill.ca/~orm/rotcal.html 【在 chopin19 的大作中提到: 】 : //在这个地方，如何验证这个算法的正确性呢？ ☆─────────────────────────────────────☆ AFX (新手上路) 于 (Wed Feb 4 14:49:45 2009) 提到: 【在 wks 的大作中提到: 】 : 哦，算法错了。 : 一开始，A走到y值最小的点，B走到y值最大的点。记录AB距离 : A走到A'，B不是走到离点A'最远的地方，而是走到离直线AA'最远的地方。记录A'B'距离 : ................... 学习了 ☆─────────────────────────────────────☆ chopin19 (肖邦在世||不懂算法) 于 (Wed Feb 4 21:12:23 2009) 提到: 没有证明阿，只是算法的pseudo code和语言叙述阿【在 wks 的大作中提到: 】 : 哦，算法错了。 : 一开始，A走到y值最小的点，B走到y值最大的点。记录AB距离 : A走到A'，B不是走到离点A'最远的地方，而是走到离直线AA'最远的地方。记录A'B'距离 : ................... ☆─────────────────────────────────────☆ wks (cloverprince) 于 (Wed Feb 4 22:23:46 2009) 提到: 感觉显然吧。距离最远的两点一定是能用一对平行线夹住、其他点在平行线内侧的两点。反证法：如果距离最远的两个点不能用平行线夹住，使得所有点在平行线内测，那么就过这两点，垂直于他们的连线，分别做一对平行线。因为刚才设这两个点不能被一对平行线夹住，所以必然存在另外一个点，在这一对平行线的外侧。再过这个外侧的点，做平行于那对平行线的第三条直线。发现了吧，第三条直线到那一对平行线中的某一条，距离比那个“距离最远的两点”还要远。矛盾。【在 chopin19 的大作中提到: 】 : 没有证明阿，只是算法的pseudo code和语言叙述阿 ☆─────────────────────────────────────☆ chopin19 (肖邦在世||不懂算法) 于 (Wed Feb 4 23:28:25 2009) 提到: 嗯，应该是这样的，谢谢哈~ 【在 wks 的大作中提到: 】 : 感觉显然吧。距离最远的两点一定是能用一对平行线夹住、其他点在平行线内侧的两点。 : 反证法：如果距离最远的两个点不能用平行线夹住，使得所有点在平行线内测， : 那么就过这两点，垂直于他们的连线，分别做一对平行线。 : ...................

[合集] 如何求凸包的最远点对？