把环倍长，只考虑$i$~$i+n$的点

发现最远点满足决策单调性

分治求解就可以了

#include
    
     using namespace std;#define ll long longinline int read(){
    	char ch=getchar();	int res=0,f=1;	while(!isdigit(ch)){
    if(ch=='-')f=-f;ch=getchar();}	while(isdigit(ch))res=(res+(res<<2)<<1)+(ch^48),ch=getchar();	return res*f;}const int N=500005;inline double P(double x){
    	return x*x;}struct point{
    	double x,y;int idx;	friend inline double dis(const point &a,const point &b){
    		return P(a.x-b.x)+P(a.y-b.y);	}}p[N];int T,n,ans[N];inline bool comp(int now,int p1,int p2){
    	ll x=dis(p[now],p[p1]),y=dis(p[now],p[p2]);	if(p1>now+n||p1
     
      now+n||p2
      
       p[p2].idx:x
       
        >1,now=st;	for(int i=st+1;i<=des;i++)if(comp(mid,now,i))now=i;	ans[mid]=p[now].idx;	if(l