http://www.lydsy.com/JudgeOnline/problem.php?id=2642
题意：
n个瞭望台，形成一个凸n边形。这些瞭望台的保护范围是这个凸包内的任意点。
敌人进攻时，会炸毁一些瞭望台，使得总部暴露在新的保护范围之外。
选择一个点作为总部，使得敌人在任何情况下需要炸坏的瞭望台数目尽量多
任何情况指，假设需炸毁m个，无论炸毁哪m个，剩下的瞭望台都不能保护总部
输出这个数目
凸壳上的点顺时针输入
若敌人只能炸一次，那么总部应选在
所有点i+2到点i组成的有向直线的左侧——半平面交
若敌人能炸两次，那么炸连续的两个点更优
炸毁连续的两个，可以使得到的半平面的左侧尽量靠边
这样交集更容易为空
同理，炸毁k个也是炸毁连续的k个
所以二分炸毁次数k，
判断所有i+k+1和点i构成的有向直线表示的半平面有没有交集即可
#include<cmath>
#include<cstdio>
#include<iostream>
#include<algorithm> using namespace std; #define N 50001 typedef long long LL; const double eps=1e-; struct Point
{
double x,y; Point(double x=,double y=):x(x),y(y) {}
}; typedef Point Vector; Point P[N]; Vector operator + (Vector A,Vector B) { return Vector(A.x+B.x,A.y+B.y); }
Vector operator - (Vector A,Vector B) { return Vector(A.x-B.x,A.y-B.y); }
Vector operator * (Vector A,double b) { return Vector(A.x*b,A.y*b); } struct Line
{
Point P;
Vector v;
double ang; Line() {}
Line(Point P,Vector v) : P(P),v(v) { ang=atan2(v.y,v.x); } bool operator < (Line L) const
{
return ang<L.ang;
}
}; Line L[N]; void read(int &x)
{
x=; int f=; char c=getchar();
while(!isdigit(c)) { if(c=='-') f=-; c=getchar(); }
while(isdigit(c)) { x=x*+c-''; c=getchar(); }
x*=f;
} double Cross(Vector A,Vector B)
{
return A.x*B.y-A.y*B.x;
} bool OnLeft(Line L,Point p)
{
return Cross(L.v,p-L.P)>;
} Point GetIntersection(Line a,Line b)
{
Vector u=a.P-b.P;
double t=Cross(b.v,u)/Cross(a.v,b.v);
return a.P+a.v*t;
} bool HalfplaneIntersection(Line *L,int n)
{
// sort(L,L+n); 顺时针输入的点，本来就按极角排好序了
Point *p=new Point[n];
Line *q=new Line[n];
int first,last;
q[first=last=]=L[];
for(int i=;i<n;++i)
{
while(first<last && !OnLeft(L[i],p[last-])) last--;
while(first<last && !OnLeft(L[i],p[first])) first++;
q[++last]=L[i];
if(fabs(Cross(q[last].v,q[last-].v))<eps)
{
last--;
if(OnLeft(q[last],L[i].P)) q[last]=L[i];
}
if(first<last) p[last-]=GetIntersection(q[last],q[last-]);
}
while(first<last && !OnLeft(q[first],p[last-])) last--;
return last-first>;
} bool check(int n,int k)
{
int m=;
for(int i=;i<n;++i) L[m++]=Line(P[i],P[i]-P[(i+k+)%n]);
return !HalfplaneIntersection(L,m);
} int main()
{
int n,x,y;
int l,r,mid,ans=;
while(scanf("%d",&n)!=EOF)
{
for(int i=;i<n;++i)
{
read(x); read(y);
P[i]=Point(x,y);
}
ans=n-;
l=; r=n-;
while(l<=r)
{
mid=l+r>>;
if(check(n,mid)) ans=mid,r=mid-;
else l=mid+;
}
cout<<ans<<'\n';
}
}