BZOJ 4520 CQOI 2016 K 원점대 (KD - tree + 더미)
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define ll long long
#define N 100010
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<'0'||c>'9')) c=getchar();return c;}
int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
int read()
{
int x=0,f=1;char c=getchar();
while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();}
while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,m,c,root,cnt;
struct point
{
int d[2];
bool operator const point&a) const
{
return d[c]<a.d[c];
}
}a[N];
struct KDTree{int ch[2],a[2][2];point p;
}tree[N];
priority_queue,greater > q;
ll sqr(int x){return 1ll*x*x;}
ll dis(point u,point v){return sqr(u.d[0]-v.d[0])+sqr(u.d[1]-v.d[1]);}
ll dis(point u,int a[2][2]){return sqr(max(u.d[0]-a[0][0],a[0][1]-u.d[0]))+sqr(max(u.d[1]-a[1][0],a[1][1]-u.d[1]));}
void build(int &k,int l,int r,int op)
{
if (l>r) return;
k=++cnt,c=op;int mid=l+r>>1;nth_element(a+l,a+mid,a+r+1);
tree[k].p=a[mid];tree[k].a[0][0]=tree[k].a[0][1]=a[mid].d[0],tree[k].a[1][0]=tree[k].a[1][1]=a[mid].d[1];
for (int i=l;i<=r;i++)
tree[k].a[0][0]=min(tree[k].a[0][0],a[i].d[0]),tree[k].a[0][1]=max(tree[k].a[0][1],a[i].d[0]),
tree[k].a[1][0]=min(tree[k].a[1][0],a[i].d[1]),tree[k].a[1][1]=max(tree[k].a[1][1],a[i].d[1]);
build(tree[k].ch[0],l,mid-1,op^1);
build(tree[k].ch[1],mid+1,r,op^1);
}
void query(int k,point p)
{
if (dis(tree[k].p,p)>=q.top()) q.push(dis(tree[k].p,p)),q.pop();
int l=tree[k].ch[0],r=tree[k].ch[1];ll u=dis(p,tree[l].a),v=dis(p,tree[r].a);
if (u<v) swap(l,r),swap(u,v);
if (l&&u>=q.top()) query(l,p);
if (r&&v>=q.top()) query(r,p);
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4520.in","r",stdin);
freopen("bzoj4520.out","w",stdout);
const char LL[]="%I64d
";
#else
const char LL[]="%lld
";
#endif
n=read(),m=read()<<1;
for (int i=1;i<=n;i++) a[i].d[0]=read(),a[i].d[1]=read();
build(root,1,n,0);
while (m--) q.push(0);
for (int i=1;i<=n;i++) query(root,a[i]);
cout<<q.top();
return 0;
}
다음으로 전송:https://www.cnblogs.com/Gloid/p/10161753.html
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.