<>

<      >

题目大意：

给出一个凸多边形，顶点为一些防御塔，保护范围是凸多形内部，不包括边界，在多边形内部选择一点，使得对方至少需要摧毁的塔防数量最多。（注意，是任意摧毁这么多数量的塔）

解题分析：

首先需要明白的是一个问题，对于摧毁一定数量的塔防，怎样的方案是使得剩下的保护范围最小。

结论是摧毁连续多个顶点，这样是最优的，可以尝试证明一下。

对于5个顶点的多边形，删除两个顶点，可以尝试连续两个顶点，以及间隔一个顶点。

由于原多边形是凸边形，所以还是比较容易得到连续顶点最优，同理可得其它情况。

题目要求的是使对方尽可能多的摧毁至少需要摧毁的塔防，联系复杂度等等问题

二分答案，然后判断是否存在一个区域，保证能受保护。

对于每一次二分，枚举删除连续的顶点，形成新的边界，通过半平面交判断是否存在可行区域。

注意：边界上的点是不受保护的，所以只需要判断多边形的核的面积即可。

           当剩余的点在2个以及以下是，是肯定可行的。避免处理麻烦。

再看一看题目的范围，5W个顶点，半平面交至少肯定是要用nlgn的算法，然而这道题连二分+nlogn算法也会卡，有一种叫做zzy的半平面交算法，是将所有向量按极角排序之后，维护了一个双端队列，排序部分达到nlgn的复杂度，其实后面只需要o(n)。然后再看这题，原先给的凸多形是有序的，而之后我们的连线的极角也是循环有序的，线性扫描一遍，找到最小的极角，便可以依次得到有序的向量，O(n)的线性sort。

这里的代码将原来的顺序调整为逆序，半平面交的算法是针对向量的左侧，而极角是顺时针有序。

 

#include
     
      #include
      
       #include
       
        #include
        
         #define eps 1e-10#define N 50005#define zero(a) (fabs(a)
         
          head+1)        q[m++]=Get_Intersect(deq[head],deq[tail]);}int slove(int mid){    if(n-mid<=2) return 1;    for(int i=0;i
         
        
       
      
     

 

 

2018-08-03