题意：给你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=1<<28; const ll INF=1ll<<60; const double Pi=acos(-1.0); const int Mod=1e9+7; const int Max=50010; struct Point { double x,y; Point(double x=0,double y=0):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)<0||zero(x-a.x)&&sgn(y-a.y)<0; } 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)>0; } 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 ",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=0]=L[0]; for(int i=0; i<n; ++i) { while(first<last && !OnLeft(L[i],p[last-1])) last--; while(first<last && !OnLeft(L[i],p[first])) first++; q[++last]=L[i]; if(zero(Cross(q[last].v,q[last-1].v))) { last--; if(OnLeft(q[last],L[i].p)) q[last]=L[i]; } if(first<last) p[last-1]=GetIntersection(q[last-1],q[last]); } while(first<last&&!OnLeft(q[first],p[last-1])) last--; // printf("%d ",last-first-1); return max(last-first-1,0); } Point tow[Max]; Line convex[Max]; int Solve(int mid,int n) { if(n-mid<=2)//剩余的点 return 0; for(int i=0; i<n; ++i) { //注意注意，半平面交为逆时针 convex[i]=Line(tow[i],tow[(i-mid-1+n)%n]-tow[i]);//关键，删除了mid个点后的半平面 } return HarfplaneIntersection(convex,n); } int Dichotomy(int lef,int rig,int n)//二分 { while(lef<rig) { int mid=(lef+rig>>1);//代表删多少个点 if(Solve(mid,n))//非空即为需要删除更多的点 { lef=mid+1; } else { rig=mid; } } return lef; } int main() { int n; while(~scanf("%d",&n)) { for(int i=0; i<n; ++i) { tow[i].read(); } printf("%d ",Dichotomy(1,n,n)); } return 0; }