2019.02.21 bzoj2739: 最远点（决策单调性+分治）

传送门

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

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

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

代码：

#include<bits/stdc++.h>
#define ri register int
using 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||x>p+n)dx=-dx;
    if(y<p||y>p+n)dy=-dy;
    return dx==dy?a[x].id>a[y].id:dx<dy;
}
inline void solve(int l,int r,int ql,int qr){
    if(l>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<<ans[i]<<'\n';
    }
    return 0;
}

巴特西

2019.02.21 bzoj2739: 最远点（决策单调性+分治）

最新文章

热门文章