题意：给你n个塔（点）形成一个顺时针的凸包，敌人可以摧毁任何塔，摧毁后剩下的塔再组成凸包
在开始的凸包内选一点为主塔，保证敌人摧毁尽量多塔时主塔都还在现在的凸包内，求出最多摧毁的塔
题解：这题关键就是选的主塔在不同的地方，敌人就会摧毁不同的塔来让你的主塔暴露
因此这样想，找出敌人摧毁不同的塔后形成的所有不同的凸包，再求出所有凸包的交就好
具体就是，首先枚举摧毁塔的个数k，再把摧毁任意k个塔所形成的所有不同的凸包求一个交，如果为空就代表了摧毁k个塔一定可以保证无论主塔在哪儿都可以暴露（关键）
而所有凸包的交可以将其转化为找到所有凸包上的直线求半平面交，接着就是注意敌人摧毁连续的k个塔一定是最优的，所以求半平面交的直线只要n条（理解一下）
最后可以发现答案满足单调性，可以二分答案
再然后这儿有个小trick就是找直线时需要逆时针找（因为半平面交是逆时针来求的）
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<iomanip>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const ll INF=1ll<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
struct Point
{
double x,y;
Point(double x=,double y=):x(x),y(y) {};
int read()
{
scanf("%lf%lf",&x,&y);
}
inline Point operator+(const Point& a)const
{
return Point(x+a.x,y+a.y);
}
inline Point operator*(double a)const
{
return Point(x*a,y*a);
}
inline Point operator-(const Point& a)const
{
return Point(x-a.x,y-a.y);
}
inline bool operator<(const Point& a)const
{
return sgn(x-a.x)<||zero(x-a.x)&&sgn(y-a.y)<;
}
inline bool operator!=(const Point& a)const
{
return !(zero(x-a.x)&&zero(y-a.y));
}
};
typedef Point Vector;
struct Line
{
Point p;
Vector v;
double ang;//极角
Line() {};
Line(Point p,Vector v):p(p),v(v)
{
ang=atan2(v.y,v.x);
}
inline bool operator<(const Line& L)const
{
return ang<L.ang;
}
};
double Dis(Point A,Point B)
{
return sqrt((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y));
}
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;
}
int HarfplaneIntersection(Line *L,int n)
{
sort(L,L+n);
// for(int i=0; i<n; ++i)
// {
// printf("%lf %lf %lf %lf\n",L[i].p.x,L[i].p.y,L[i].v.x,L[i].v.y);
// }
int first,last;
Point *p=new Point[n];
Line *q=new Line[n];
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(zero(Cross(q[last].v,q[last-].v)))
{
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--;
// printf("%d\n",last-first-1);
return max(last-first-,);
}
Point tow[Max];
Line convex[Max];
int Solve(int mid,int n)
{
if(n-mid<=)//剩余的点
return ;
for(int i=; i<n; ++i)
{
//注意注意，半平面交为逆时针
convex[i]=Line(tow[i],tow[(i-mid-+n)%n]-tow[i]);//关键，删除了mid个点后的半平面
}
return HarfplaneIntersection(convex,n);
}
int Dichotomy(int lef,int rig,int n)//二分
{
while(lef<rig)
{
int mid=(lef+rig>>);//代表删多少个点
if(Solve(mid,n))//非空即为需要删除更多的点
{
lef=mid+;
}
else
{
rig=mid;
}
}
return lef;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
for(int i=; i<n; ++i)
{
tow[i].read();
}
printf("%d\n",Dichotomy(,n,n));
}
return ;
}