原题地址 http://poj.org/problem?id=2839
有点忙…… 题解就简单写吧……
大概就是给一个点数10W的凸包…… 然后要支持查询某个三角形与凸包的交面积…… 查询规模也是10W……
这个显然要找出对数级别的算法……
首先要把凸包的基本操作支持起来…… 现在假设凸包已经建好了…… 木有重点木有三点共线，逆时针排过序了……
然后查询一条线段与凸包的交点数目（严格相交）…… 这个相当于求直线与凸包的交点……
于是关键就是快速找到直线与哪两条线段相交…… 一个显然的观察是叉积必然一段正的一段负的…… 交界处就是交的那条线段（这里为简单其间不讨论平行、重叠、非正规相交等蛋疼情况…… 当然代码还是要考虑的……）……
然后我们发现只要在正的一段中找到一个点…… 负的一段中找到一个点…… 那么就满足二分要求，直接二分找临界点就可以了……
然后可以发现这样一个事实…… 就是距离这条直线最远的两个点必然是满足要求的一正一负的两个点……
显然凸包上点到直线距离这个东西是单峰的（假如只考虑某个半凸包的话）…… 而且连接峰值点的那两条线段斜率正好把查询的这条直线的斜率夹在中间，这样往后走或者往前走距离都会减少，于是这个点就最大了……
于是先把N条边按斜率排序…… 然后二分查找两次，找到一正一负两个峰值点…… 然后判断这两个峰值点的连线段是不是和这条直线相交…… 如果不想交那直线就在凸包外，就直接木有交点了
否则以峰值点为边界，再二分两次…… 找到临界点…… 非正规相交、平行等蛋疼情况自行处理……
这样一条线段与凸包的交点数目就在O(lgN)级别完成了……
然后判定一个点是否在凸包内…… 这个就很简单了，这个点与无穷远点连线段，用上面的方法判定交点个数就行了…… 也能做到O(lgN)……
然后还有个技术问题就是求一条直线（两端点在凸包端点上）切割凸包后某一侧的面积…… 这个可以用线段树解决……
S(a,b)表示点a和b的连直线切出来的的逆时针方向面积……
则显然S(a,b)=S(a,mid)+S(mid,b)+Triangle_Area(a,mid,b)…… 这里就是普通的无向面积……
然后就用线段树维护吧…… 这样切割出的面积查询也是O(lgN)……
再然后……查询一条任意直线切割凸包的面积…… 这个很简单…… 就是分解成上一个问题加上一个四边形面积…… 这样就行了…… 注意跨越N的情况处理……
然后要特判三角形和凸包的包含关系……（同样，简单起见，边界情况不讨论，写代码时自行考虑）
三角形与凸包交面积为0当且进当三角形三边与凸包无交点，三点在凸包外，且凸包上任意一点在三角形外。
三角形与凸包交面积为凸包面积当且进当三角形三边与凸包无交点，三点在凸包外，且凸包上任意一点在三角形内。
三角形与凸包交面积为三角形面积当且进当三角形三边与凸包无交点且三点在凸包内。
剩下的就是常规情况了……
可以在纸上自己画图…… 分成一块块计算…… 都可以表示成查询一条任意直线切割凸包的面积这样的形式…… 某个面积是否存在取决于某条边是否与凸包相交…… 或者某个点是否在凸包以内…… 注意起点终点相同的话面积要舍弃之类的特判……
然后就写代码吧…… 我写了14+K…… 调了3天才AC……
代码不贴。 因为我也不保证考虑到了所有的特判所有的情况，只是AC了而已。 为防误人子弟就不贴了。
好像还是写了很多的样子…… T_T