zcmimi's blog
avatar
zc
2020-04-15 00:06:00
  • 本文总阅读量
查看原题

点击跳转

#include<bits/stdc++.h>
typedef long long ll;
#define fur(i,x,y) for(int i(x);i<=y;++i)
namespace IO{const int str=1<<20;static char in_buf[str],*in_s,*in_t;bool __=0;char gc(){return (in_s==in_t)&&(in_t=(in_s=in_buf)+fread(in_buf,1,str,stdin)),in_s==in_t?EOF:*in_s++;}void in(char &ch){if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF)__=1;else ch=c;}void in(char *ch){*ch='\0';if(__)return;char c;while((c=gc())!=EOF&&isspace(c));if(c==EOF){__=1;return;}*ch=c;ch++;while((c=gc())!=EOF&&!isspace(c))*ch=c,ch++;if(c==EOF)__=1;*ch='\0';}template<typename T>void in(T &x){if(__)return;char c=gc();bool f=0;while(c!=EOF&&(c<'0'||c>'9'))f^=(c=='-'),c=gc();if(c==EOF){__=1;return;}x=0;while(c!=EOF&&'0'<=c&&c<='9')x=x*10+c-48,c=gc();if(c==EOF)__=1;if(f)x=-x;}template<typename T,typename ... arr>void in(T &x,arr & ... y){in(x),in(y...);}const char ln='\n';static char out_buf[str],*out_s=out_buf,*out_t=out_buf+str;void flush(){fwrite(out_buf,1,out_s-out_buf,stdout);out_s=out_buf;}void pt(char c){(out_s==out_t)?(fwrite(out_s=out_buf,1,str,stdout),*out_s++=c):(*out_s++=c);}void out(const char* s){while(*s)pt(*s++);}void out(char* s){while(*s)pt(*s++);}void out(char c){pt(c);}template<typename T>void out(T x){if(!x){pt('0');return;}if(x<0)pt('-'),x=-x;char a[50],t=0;while(x)a[t++]=x%10,x/= 10;while(t--)pt(a[t]+'0');}template<typename T,typename ... arr>void out(T x,arr & ... y){out(x),out(y...);}}using namespace IO;
const int N=100011;const ll inf=1ll<<63;
int rt,id,ls[N],rs[N];
int L[N],R[N],D[N],U[N];
struct node{int x,y;}t[N];
bool cmpx(node p,node q){return p.x<q.x;}
bool cmpy(node p,node q){return p.y<q.y;}
template<class T>T min(T x,T y){return x<y?x:y;}
template<class T>T max(T x,T y){return x>y?x:y;}
ll sq(int x){return 1ll*x*x;}
void upd(int x,int y){
    L[x]=min(L[x],L[y]),R[x]=max(R[x],R[y]),
    D[x]=min(D[x],D[y]),U[x]=max(U[x],U[y]);
}
void pu(int x){
    L[x]=R[x]=t[x].x;
    D[x]=U[x]=t[x].y;
    if(ls[x])upd(x,ls[x]);
    if(rs[x])upd(x,rs[x]);
}
int build(int l,int r){
    if(l>r)return 0;
    int m=l+r>>1;
    double ax=0,ay=0,vx=0,vy=0;
    fur(i,l,r)ax+=t[i].x,ay+=t[i].y;
    ax/=r-l+1,ay/=r-l+1;
    fur(i,l,r)
        vx+=sq(ax-t[i].x),
        vy+=sq(ay-t[i].y);
    std::nth_element(t+l,t+m,t+r+1,vx>vy?cmpx:cmpy);
    ls[m]=build(l,m-1);rs[m]=build(m+1,r);pu(m);
    return m;
}
std::priority_queue<ll,std::vector<ll>,std::greater<ll>>q;
ll dis(int x){return sq(t[x].x-t[id].x)+sq(t[x].y-t[id].y);}
ll f(int x){
    return max(sq(L[x]-t[id].x),sq(R[x]-t[id].x))+
           max(sq(D[x]-t[id].y),sq(U[x]-t[id].y));
}
void qry(int x){
    if(!x)return;
    ll res=dis(x),ld=inf,rd=inf;
    if(x!=id&&res>q.top())q.pop(),q.push(res);
    if(ls[x])ld=f(ls[x]);
    if(rs[x])rd=f(rs[x]);
    if(ld<rd){
        if(ld>q.top())qry(ls[x]);
        if(rd>q.top())qry(rs[x]);
    }
    else{
        if(rd>q.top())qry(rs[x]);
        if(ld>q.top())qry(ls[x]);
    }
}
int main(){
    int n,k;
    in(n,k);
    fur(i,1,n)in(t[i].x,t[i].y);
    rt=build(1,n);
    k<<=1;while(k--)q.push(-1);
    fur(i,1,n)id=i,qry(rt);
    printf("%lld\n",q.top());
}
LG 4357 [CQOI2016]K远点对
comment评论
Search
search