BZOJ2739 : 最远点

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

把环倍长，设$w(i,j)$表示对于$i$，决策$j$的价值，如果$j$在$[i,i+n]$，那么$w(i,j)=dis(i,j)$，否则$w(i,j)=-dis(i,j)$。

则$w$满足四边形不等式，最优决策满足完全单调性，分治求解即可。

时间复杂度$O(n\log n)$。

#include<cstdio>

#define N 500010

int T,n,i,f[N];struct P{int x,y,p;}a[N<<1];

inline void read(int&a){

  char c;bool f=0;a=0;

  while(!((((c=getchar())>='0')&&(c<='9'))||(c=='-')));

  if(c!='-')a=c-'0';else f=1;

  while(((c=getchar())>='0')&&(c<='9'))(a*=10)+=c-'0';

  if(f)a=-a;

}

inline bool cmp(int i,int j,int k){

  long long x=1LL*(a[i].x-a[j].x)*(a[i].x-a[j].x)+1LL*(a[i].y-a[j].y)*(a[i].y-a[j].y),

            y=1LL*(a[i].x-a[k].x)*(a[i].x-a[k].x)+1LL*(a[i].y-a[k].y)*(a[i].y-a[k].y);

  if(j<i||j>i+n)x=-x;

  if(k<i||k>i+n)y=-y;

  return x==y?a[j].p>a[k].p:x<y;

}

void solve(int l,int r,int dl,int dr){

  int mid=(l+r)>>1,dm=dl;

  for(int i=dl+1;i<=dr;i++)if(cmp(mid,dm,i))dm=i;

  f[mid]=a[dm].p;

  if(l<mid)solve(l,mid-1,dl,dm);

  if(r>mid)solve(mid+1,r,dm,dr);

}

int main(){

  read(T);

  while(T--){

    read(n);

    for(i=1;i<=n;i++)read(a[i].x),read(a[i].y),a[i].p=i,a[n+i]=a[i];

    solve(1,n,1,n+n);

    for(i=1;i<=n;i++)printf("%d\n",f[i]);

  }

  return 0;

}