半平面交第一次真的好难写啊。。前后加起来起码弄了7小时。

半平面交的算法思想并不复杂：

    1、将所有向量按极角大小从小到大排序，向量(x,y)的极角=atan2(y,x)，当两个向量的极角相等时选择性的保留在较左边的那个

    2、运用一种数据结构：双端队列，用phead表示双端队列的头位置，pend表示双端队列的尾位置，初始化时phead=0，pend=-1

         然后开始一个一个添加已经排好序的向量进双端队列中：

         设当前要添加的向量是v

         #当双端队列中的向量数量大于等于2时（pend-phead>=1) 并且 双端队列最尾部的两个向量的交点在向量v所表示的半平面外，删除位于双端队列最尾部的那个向量（pend--) 

        #当双端队列中的向量数量大于等于2时 并且 双端队列最头部的两个向量的交点在向量v所表示的半平面外，删除位于双端队列最头部的那个向量（phead++）

        进行外上面两个步骤后，添加当前向量v到双端队列的尾部

    3、当排好序的向量全部添加完之后，还需要一次判定，过程和上一步类似：

        #当双端队列中的向量数量大于2时，如果双端队列尾部的两个向量的交点在 最头部的向量所表示的半平面外，删除位于双端队列最尾部的那个向量

        #当双端队列中的向量数量大于2时，如果双端队列头部的两个向量的交点在 最尾部的向量所表示的半平面外，删除位于双端队列最头部的那个向量

    4、依次求双端队列相邻两个向量的交点 即为 所有半平面的交围成的凸多边形的顶点（当然也有可能是非封闭图形或者线段、点，甚至是空集）

有一个非常重要的地方一定要注意：

每次一定要先判断双端队列最尾部的向量该不该删，再判断双端队列头部的向量该不该删。因为双端队列中的向量的极角是从小到大有序的，当新插入一个向量v时，应该先考虑与向量v的极角最相近的向量该不该删。

贴一个自己的半平面交的模板：（POJ2451标程）

1 #include
        
          2 #include
         
           3 #include
          
            4 #include
           
             5 #include
            
              6 #define maxn 20005 7 #define EPS 1e-10 8 using namespace std; 9 int n,sum;10 int phead=0,pend=-1;11 struct Point{
      double x,y;};12 13 struct VecLine{14        double x0,y0,vx,vy;     //(x0,y0)表示该向量上的一点，(vx,vy)表示该向量的方向15        double angle;16        friend bool operator<(const VecLine a,const VecLine b){17               if(fabs(a.angle-b.angle)<=EPS){18                                    double x1=a.vx,y1=a.vy;19                                    double x2=b.x0-a.x0,y2=b.y0-a.y0;20                                    return (x1*y2-x2*y1<0);21               }22               return a.angle
             
              EPS) line[++tot]=line[i];45 46 }47 sum=++tot; 48 49 }50 Point Get_cross_point(VecLine A,VecLine B){51 double x0=A.x0,y0=A.y0,x1=A.vx,y1=A.vy;52 double x2=B.x0,y2=B.y0,x3=B.vx,y3=B.vy;53 double k=(y2*x1+y1*x0-x1*y0-y1*x2)/(x3*y1-y3*x1);54 double x=x2+k*x3,y=y2+k*y3;55 return ((Point){x,y});56 }57 58 bool Judge(VecLine A,VecLine B,VecLine C){ //Judge函数用于判断向量A和向量B的交点是否在向量C的左侧59 Point p=Get_cross_point(A,B); 60 p.x=p.x-C.x0;p.y=p.y-C.y0;61 return (p.x*C.vy-p.y*C.vx<0);62 }63 64 void Get_Half_Plane(){65 for(int i=0;i
              
               =1 && !Judge(deque[pend],deque[pend-1],X)) pend--;68 while((pend-phead)>=1 && !Judge(deque[phead],deque[phead+1],X)) phead++;69 pend++;deque[pend]=X;70 }71 while((pend-phead)>=2 && !Judge(deque[pend],deque[pend-1],deque[phead])) pend--;72 while((pend-phead)>=2 && !Judge(deque[phead],deque[phead+1],deque[pend])) phead++; 73 } 74 void GetArea(){75 double S=0;76 Point ans[maxn];77 int t=0;78 for(int i=phead;i<=pend;i++){79 int j=i+1;if (j>pend) j=phead;80 ans[t++]=Get_cross_point(deque[i],deque[j]);81 82 }83 ans[t]=ans[0];84 for(int i=0;i