bzoj 2739 最远点

Description

　　给你一个N个点的凸多边形，求离每一个点最远的点。

Input

　　本题有多组数据，第一行一个数T，表示数据组数。
　　每组数据第一行一个数N，表示凸多边形点的个数，接下来N对数，依次表示1~N这N个点的坐标，按照逆时针给出。

Output

　　对于每组数据输出N个数，第i个数表示离第i个点最远的点的编号，如果有多个最远点，输出编号最小的。

将点倍长，若点j在点i的[i,i+n]内，w[i,j]=dis[i,j],否则w[i,j]=-dis[i,j];

最优决策满足单调性，分治；

#include<bits/stdc++.h>

#define ll long long

#define inf 0x7fffffff

using namespace std;

inline int read(){

    int s=,f=;char ch=getchar();

    for(;ch<''||ch>'';ch=getchar())if(ch=='-')f=-;

    for(;ch>=''&&ch<='';ch=getchar())s=s*+ch-'';

    return s*f;

}

inline void print(int x){

    if(!x)return;

    print(x/);

    putchar(x%+'');

}

int ans[];

struct node{int x,y,id;}a[];

int n;

ll sqr(ll x){return x*x;}

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

    ll x=sqr(a[i].x-a[j].x)+sqr(a[i].y-a[j].y);

    ll y=sqr(a[i].x-a[k].x)+sqr(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].id>a[k].id:x<y;

}

void solve(int L,int R,int l,int r){

    int mid=(L+R)>>;int k=l;

    for(int i=l+;i<=r;++i)if(cmp(mid,k,i))k=i;

    ans[mid]=a[k].id;

    if(L<mid)solve(L,mid-,l,k);

    if(R>mid)solve(mid+,R,k,r);

}

int main(){

    int T;T=read();

    for(;T;--T){

        n=read();

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

        solve(,n,,n+n);

        for(int i=;i<=n;++i)

            print(ans[i]),puts("");

    }return ;

}