Becoming a member of ACM !
今天打开gmail时发现一封acmhelp发的邮件，点开来居然是membership的邀请信！
Dear ICPC Participant: As an ACM-ICPC participant, the Association for Computing Machinery (ACM) is delighted to offer you ACM Student Membership for one year at no cost
感觉很是幸运，遥想起去年去武汉打酱油的日子。。。
本来早就想写写武汉的点点滴滴，不过还是忍住了，学习诸位神牛，等到真的退役了再去回味回味吧
到ACM的homepage看了看，有几句话是给member的：
- Advancing the art, science, engineering, and application of information technology
- Fostering the open interchange of information to serve both professionals and the public; and
- Promoting the highest professional and ethical standards.
看了之后一边感到胸中膨胀起一个coder的自豪感，一边为我一周后的六级担忧。。。
半平面交的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
