HDU 3761 Jungle Outpost（二分+半平面交）
转载请注明出处，谢谢http://blog.csdn.net/acm_cxlove/article/details/7854526 by---cxlove
题目：给出一个凸多边形，顶点为一些防御塔，保护范围是凸多形内部，不包括边界，在多边形内部选择一点，使得对方至少需要摧毁的塔防数量最多。
http://acm.hdu.edu.cn/showproblem.php?pid=3761
首先感谢晴天哥哥的悉心指导。
首先需要明白的是一个问题，对于摧毁一定数量的塔防，怎样的方案是使得剩下的保护范围最小。
结论是摧毁连续多个顶点，这样是最优的，可以尝试证明一下。
对于5个顶点的多边形，删除两个顶点，可以尝试连续两个顶点，以及间隔一个顶点。
由于原多边形是凸边形，所以还是比较容易得到连续顶点最优，同理可得其它情况。
题目要求的是使对方尽可能多的摧毁至少需要摧毁的塔防，联系复杂度等等问题
二分答案，然后判断是否存在一个区域，保证能受保护。
对于每一次二分，枚举删除连续的顶点，形成新的边界，通过半平面交判断是否存在可行区域。
注意：边界上的点是不受保护的，所以只需要判断多边形的核的面积即可。
当剩余的点在2个以及以下是，是肯定可行的。避免处理麻烦。
再看一看题目的范围，5W个顶点，半平面交至少肯定是要用nlgn的算法，其实听了晴天哥哥的说明，才知道，这题
二分+半平面交的nlgnlgn的算法都要卡掉，顿时吓尿了，难道有o(n)的半平面交算法？？？
多亏晴天哥哥的指导，其实zzy的半平面交算法是将所有向量按极角排序之后，维护了一个双端队列，排序部分达到nlgn的复杂度，其实后面只需要o(n)。然后再看这题，原先给的凸多形是有序的，而之后我们的连线的极角也是循环有序的，线性扫描一遍，找到最小的极角，便可以依次得到有序的向量，O(n)的线性sort,晴天哥哥太神了。
具体细节就要看每个人的习惯了，我将原来的顺序调整为逆序，半平面交的算法是针对向量的左侧，而极角是顺时针有序。
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#define eps 1e-10#define N 50005#define zero(a) (fabs(a)<eps)using namespace std;struct Point { double x,y; Point(){} Point(double tx,double ty){x=tx;y=ty;}}p[N],q[N];int n,m;struct Segment{ Point s,e; double angle; void get_angle(){angle=atan2(e.y-s.y,e.x-s.x);}}seg[N];double xmul(Point p0,Point p1,Point p2){ return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}double Get_Area(Point pt[],int n){ double area=0; for(int i=1;i<n-1;i++) area+=xmul(pt[0],pt[i],pt[i+1]); return fabs(area)/2;}Point Get_Intersect(Segment s1,Segment s2){ double u=xmul(s1.s,s1.e,s2.s),v=xmul(s1.e,s1.s,s2.e); Point t; t.x=(s2.s.x*v+s2.e.x*u)/(u+v);t.y=(s2.s.y*v+s2.e.y*u)/(u+v); return t;}void HalfPlaneIntersect(Segment seg[],int n){ int idx; for(int i=0;i<n;i++) if(seg[i].angle+eps<seg[(i+1)%n].angle&&seg[i].angle+eps<seg[(i-1+n)%n].angle){ idx=i; break; } Segment deq[N]; deq[0]=seg[idx];deq[1]=seg[(idx+1)%n]; int head=0,tail=1; idx=(idx+2)%n; for(int i=2;i<n;i++,idx=(idx+1)%n){ while(head<tail&&xmul(seg[idx].s,seg[idx].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--; while(head<tail&&xmul(seg[idx].s,seg[idx].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++; deq[++tail]=seg[idx]; } while(head<tail&&xmul(deq[head].s,deq[head].e,Get_Intersect(deq[tail],deq[tail-1]))<-eps) tail--; while(head<tail&&xmul(deq[tail].s,deq[tail].e,Get_Intersect(deq[head],deq[head+1]))<-eps) head++; m=0; if(tail==head) return; for(int i=head;i<tail;i++){ q[m++]=Get_Intersect(deq[i],deq[i+1]); } if(tail>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<n;i++){ seg[i].s=p[i]; seg[i].e=p[(i+mid+1)%n]; seg[i].get_angle(); } HalfPlaneIntersect(seg,n); return zero(Get_Area(q,m));}int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lf%lf",&p[i].x,&p[i].y); for(int i=1;i<=n/2;i++) swap(p[i],p[n-i]); int ans,low=0,high=n,mid; while(low<=high){ mid=(low+high)/2; if(slove(mid)){ans=mid;high=mid-1;} else low=mid+1; } printf("%d\n",ans); } return 0;}