hdu 3982 Harry Potter and J.K.Rowling（半平面交+求凸多边形和圆的面积交）

hdu 3982 Harry Potter and J.K.Rowling（半平面交+求凸多边形和圆的面积交）

 昨晚到现在，终于A掉，上午在J2EE课上想清楚了，不过下午还是拍着数据才调出来BUG的 = =。。。这水平。。。到区域赛遇到计算几何神题肿么办吧。

这题一看就有思路啊，很裸的思路，先求半平面交（交得的面积是樱桃所在的那个大块块），然后求得的多边形和圆形求交。

1、半平面交的话，需要把线段方向改下，都变成有效区域为樱桃所在区域。

2、有一个坑就是如果切痕都切不到蛋糕，是需要输出100%的，直接特判下。

3、半平面交我用的N*LOGN的算法，这个就不多说了。但是记得需要初始化区域，我的区域是(-2*r, -2*r) --- (2*r, 2*r)，这个矩形区域。

关键是求多边形和圆形的交。经过半平面交，交的多边形一定是凸多边形，那么就计算凸多边形和圆形的交。

先求出凸多边形和圆的交点（包括在凸多边形在圆内的顶点），根据樱桃位置极角排序。

然后找到第一个顶点为起始顶点，找相邻顶点和第一个顶点组成的三角形，这个三角形一定是内部的面积。

关键是找弓形面积，如下图，蓝色线表示的是多边形和圆形围城的区域，最终和圆的交点应该是B D E。

当计算到DE这条线段时，做DE的中垂线，交圆与BC（绿色点），判断C或者B是否在多边形内部，如果在的话，说明弓形DE是需要计算的面积。

这里有个计算下面面积和上面面积之分。因为我的计算默认的是逆时针，所以我的计算的有效面积一定是左侧面积，如果需要计算弓形面积，那么计算的一定是DE右侧的面积（这个需要好好想下），然后就需要判断DE是优弧还是劣弧，如果是圆心在DE的右侧，则是优弧，反之为劣弧。这个用叉积判断下就好。

注意计算角度不能用asin - -。。。asin的范围是[-π/2, π/2]。。。（哎，我是挫人。。。）

还有就是，如果最后只是两个交点，注意不要计算两次。。。T T。。可以把线段变换下（因为只有两个点的话，需要保证樱桃在线段的右侧）

#include <set>
#include <map>
#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>
#define MID(x,y) ( ( x + y ) >> 1 )
#define L(x) ( x <