半平面交的O(nlogn)算法[zhuan]
求n个半平面的交有三种做法：
第一种就是用每个平面去切割已有的凸多边形，复杂度O(n^2)。
第二种就是传说中的分治算法。将n个半平面分成两个部分，分别求完交之后再将两个相交的区域求交集。由于交出来的都是凸多边形，利用凸多边形的交可以在O(n)时间内完成的性质，将复杂度降为O(nlogn)。
第三种就是ZZY大牛的那篇论文提到的他自创的排序增量算法。但是他的那种做法还是有些复杂，在网上找到evalls写的一个很优美的版本：（原文地址：http://evalls.yo2.cn/articles/%E5%8D%8A%E5%B9%B3%E9%9D%A2%E4%BA%A4onlogn%E7%9A%84%E7%AE%97%E6%B3%95.html）
step1. 将所有半平面按极角排序，对于极角相同的，选择性的保留一个。 O(nlogn)
step2. 使用一个双端队列(deque)，加入最开始2个半平面。
step3. 每次考虑一个新的半平面：
a.while deque顶端的两个半平面的交点在当前半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在当前半平面外:删除deque底部的半平面
c.将新半平面加入deque顶端
step4.删除两端多余的半平面。
具体方法是：
a.while deque顶端的两个半平面的交点在底部半平面外:删除deque顶端的半平面
b.while deque底部的两个半平面的交点在顶端半平面外:删除deque底部的半平面
重复a,b直到不能删除为止。
step5:计算出deque顶端和底部的交点即可。
这个算法描述的非常清晰。当初写的时候有两个地方想的不太明白：step 1如何选择性的保留一个。step3如何判断交点在半平面外。
其实这两个问题都可以用叉积来解决。首先根据给定的两点顺序规定好极角序。假定两点o1o2的输入方向是顺时针，那么另一点P是否在其平面内只要判 断o1P这个向量是否在o1o2这个向量的右手边即可。对于相同角度的两个半平面(a1a2，b1b2)，可以看a1b1这个向量是否在a1a2这个向量 的右手边，每次都要选择更靠近右手边的那个半平面。
利用这个算法求多边形的核（PKU 1279），0.00MS，速度还是很快的。
roselone
2009年8月23日 06:55
这篇文章写得很好。楼上也是学生吧？上POJ做题。
2009年8月24日 04:50
@MasterLuo: 是滴，这篇文章是转的，刚看完zzy的论文，然后在网上搜到的一个跟简洁的版本～
2010年9月07日 06:56
能不能发这个代码给我
2010年9月07日 06:57
邮箱837069122@qq.com
2023年7月25日 23:50
Der Download des WhatsApp-Status ist über die Tools oder Anwendungen auf Ihrem Smartphone möglich. Sie benötigen keine Drittanbieteranwendung, um WhatsApp-Statusvideos oder -bilder auf Ihrem Android oder iPhone zu speichern. whatsapp fotos aus status speichern Aber die Drittanbieter-App wird verwendet, um den WhatsApp-Status einfach herunterzuladen. WhatsApp-Storys Statusinformationen Fotos oder Videos auf dem Telefon. Aber beide werden innerhalb von 24 Stunden gelöscht. Sie können sie also aus einem anderen Ordner kopieren und an einem sicheren Ort speichern.
2023年9月15日 16:56
SCERT Bihar 2nd Class Provides the Syllabus for All the This new Syllabus are Designed Strategically by a Team of Subject Experts and are Prescribed by the Bihar State Government, Bihar Primary level Syllabus 2024 for SCERT Bihar 2nd Class Syllabus 2024 the children of Bihar has been developed with the supervision of the Bihar State Textbook Publishing Corporation Ltd, Patna Altogether Seventeen Subjects Syllabus Covering Mathematics, Hindi Language, English as Second Language and Environmental Science have been Prepared, These Syllabus are Freely Distributed under SSA Programme to the Primary Children of Bihar.
2024年1月10日 23:56
JNANABHUMI AP provides a CBSE syllabus for all classes for the academic year 2024 has been designed as per the guidelines of the CBSE Board. The syllabus offers a conceptual background and lays the groundwork for the Class 10 Board exams. jnanabhumiap.in By visiting the page, students will find the downloadable pdf of the reduced CBSE 10th Syllabus along with the deleted portion of the syllabus for each subject. So, students are advised to prepare for the exam, as per the syllabus mentioned here.