题意简述：给一个N个点的凸多边形，求离每一个点最远的点。

---

思路：先根据初中数学知识证明决策是满足单调性的，然后上分治优化即可。

才不是因为博主懒得写二分+栈优化呢

代码：

#include
    
     #define ri register intusing namespace std;inline int read(){
        int ans=0;    bool f=1;    char ch=getchar();    while(!isdigit(ch)){
    if(ch=='-')f^=1;ch=getchar();}    while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();    return f?ans:-ans;}typedef long long ll;const int N=5e5+5;int n,ans[N];struct pot{
    int x,y,id;}a[N<<1];inline ll dist(const pot&a,const pot&b){
    return (ll)(a.x-b.x)*(a.x-b.x)+(ll)(a.y-b.y)*(a.y-b.y);}inline bool check(const int&p,const int&x,const int&y){
        ll dx=dist(a[p],a[x]),dy=dist(a[p],a[y]);    if(x
     
      p+n)dx=-dx;    if(y
      
       p+n)dy=-dy;    return dx==dy?a[x].id>a[y].id:dx
       
        r||ql>qr)return;    int mid=l+r>>1,qmid=ql;    for(ri i=ql+1;i<=qr;++i)if(check(mid,qmid,i))qmid=i;    ans[mid]=a[qmid].id;    solve(l,mid-1,ql,qmid),solve(mid+1,r,qmid,qr);}int main(){
        for(ri tt=read();tt;--tt){
            n=read();        for(ri i=1;i<=n;++i)a[i].x=read(),a[i].y=read(),a[i].id=i,a[i+n]=a[i];        solve(1,n,1,n<<1);        for(ri i=1;i<=n;++i)cout<
        
         <<'\n';    }    return 0;}