传送门

半平面交。

首先，由显然成立法可以证明炸连续的几个总比分散火力效果更佳。

所以二分答案，转化为判定问题，即间隔$ans$个点的连线的半平面交是否为空。

半平面交判定即可。

时间复杂度：$O(Nlog^2N)$

//UVaLive4992//by Cydiater//2017.2.1#include <iostream>#include <cstdio>#include <cstring>#include <string>#include <cmath>#include <ctime>#include <cstdlib>#include <queue>#include <map>#include <algorithm>#include <iomanip>#include <bitset>#include <set>#include <vector>using namespace std;#define ll 		long long#define up(i,j,n)	for(int i=j;i<=n;i++)#define down(i,j,n)	for(int i=j;i>=n;i--)#define cmax(a,b)	a=max(a,b)#define cmin(a,b)	a=min(a,b)#define db		double#define Vector 		Pointconst int MAXN=1e5+5;const int oo=0x3f3f3f3f;const db eps=1e-10;inline int read(){	char ch=getchar();int x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}int dcmp(db x){if(fabs(x)<eps)return 0;else return x<0?-1:1;}struct Point{	db x,y;	Point(db x=0,db y=0):x(x),y(y){}};Vector operator + (Point x,Point y){return Vector(x.x+y.x,x.y+y.y);}Vector operator - (Point x,Point y){return Vector(x.x-y.x,x.y-y.y);}Vector operator * (Vector x,db p){return Vector(x.x*p,x.y*p);}Vector operator / (Vector x,db p){return Vector(x.x/p,x.y/p);}bool operator < (const Vector &x,const Vector &y){return dcmp(x.x-y.x)==0?x.y<y.y:x.x<y.x;}bool operator == (const Vector &x,const Vector &y){return dcmp(x.x-y.x)==0&&dcmp(x.y-y.y)==0;}struct Line{	Point P;	Vector v;	db ang;	Line(){}	Line(Point P,Vector v):P(P),v(v){ang=atan2(v.y,v.x);}};bool operator < (const Line &x,const Line &y){return x.ang<y.ang;}Point V[MAXN],P[MAXN];int N,top,head,tail;Line L[MAXN],q[MAXN];namespace solution{	Point Write(){db x=read(),y=read();return Point(x,y);}	db Cross(Vector x,Vector y){return x.x*y.y-x.y*y.x;}	bool Onleft(Point P,Line Li){return dcmp(Cross(P-Li.P,Li.v))<0;}	void Prepare(){		V[0]=Write();		down(i,N-1,1)V[i]=Write();	}	void Modify(int siz){		up(i,0,N-1)L[i]=Line(V[i],V[(i+siz)%N]-V[i]);	}	Point LineMeet(Line x,Line y){		db t=Cross(y.v,x.P-y.P)/Cross(x.v,y.v);		return x.P+x.v*t;	}	bool check(){		head=1;tail=0;q[++tail]=L[0];		up(i,1,N-1){			while(head<tail&&!Onleft(P[tail-1],L[i]))tail--;			while(head<tail&&!Onleft(P[head],L[i]))head++;			q[++tail]=L[i];			if(dcmp(q[tail-1].ang-q[tail].ang)==0){				tail--;				if(Onleft(L[i].P,q[tail]))q[tail]=L[i];			}			if(head<tail)P[tail-1]=LineMeet(q[tail-1],q[tail]);		}		while(head<tail&&!Onleft(P[tail-1],q[head]))tail--;		return tail-head>1;	}	void Solve(){		int leftt=0,rightt=N-1,mid;		while(leftt+1<rightt){			mid=(leftt+rightt)>>1;			Modify(mid);			if(check())	leftt=mid;			else		rightt=mid;		}		Modify(rightt);		if(check())	cout<<rightt<<endl;		else		cout<<leftt<<endl;	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	while(scanf("%d",&N)!=EOF){		Prepare();		Solve();	}	return 0;}

UVaLive4992:Jungle Outpost