注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ2053]SRM199 ClosestPoints  

2015-06-02 21:13:20|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

2053: SRM199 ClosestPoints

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 69  Solved: 20
[Submit][Status][Discuss]

Description

给出N,Range,Seed_0,按照Seed_{i+1} = (Seed_i * 16807) mod (2^31-1)以及Rand_i = (Seed_i mod (2 * Range)) – Range的规则,计算出Rand_1 到Rand_{3n} 。定义三维空间内的点P_k的坐标为(Rand_{3k-2}, Rand_{3k-1}, Rand_{3k}){1≤k≤n}。求出所有点中两点间最小距离的平方以及有多少对点的距离等于最小距离。 2 ≤ N ≤ 150000,1 ≤ Range ≤ 10^6,1 ≤ Seed ≤ 10^3 

注意:如果有多个点重合,就当成一个点

Sample Input

3 100 1

Sample Output

9163 1

HINT

The three points are: (-93, -51, -27), (-42, 30, -28), and (44, -22, 23). The closest pair of points are the first and third, and the square of their distance is 9163. There is 1 pair of points with a squared distance of 9163.

Source

Solution

kdtree直接上

Code

/**************************************************************
    Problem: 2053
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:1444 ms
    Memory:9012 kb
****************************************************************/
 
#include<cstdio>
#include<algorithm>
int n,range,i,D,rt,x,y,z;long long seed,max,cnt;
struct P{int d[3];}p[150010];
bool cmp(const P&a,const P&b){return a.d[0]<b.d[0]||a.d[0]==b.d[0]&&(a.d[1]<b.d[1]||a.d[1]==b.d[1]&&a.d[2]<b.d[2]);}
bool operator<(const P&a,const P&b){return a.d[D]<b.d[D];}
bool operator==(const P&a,const P&b){return a.d[0]==b.d[0]&&a.d[1]==b.d[1]&&a.d[2]==b.d[2];}
struct T{int d[3],x[2],y[2],z[2],s[2];}t[150010];
#define ls t[o].s[0]
#define rs t[o].s[1]
#define cmax(a,b) (a<b?a=b:1)
#define cmin(a,b) (a>b?a=b:1)
void mt(int o,int s){
    cmin(t[o].x[0],t[s].x[0]),cmax(t[o].x[1],t[s].x[1]);
    cmin(t[o].y[0],t[s].y[0]),cmax(t[o].y[1],t[s].y[1]);
    cmin(t[o].z[0],t[s].z[0]),cmax(t[o].z[1],t[s].z[1]);
}
int rand(){
    seed=(seed*16807)%2147483647;
    return seed%(2*range)-range;
}
int bt(int l,int r,int d){
    D=d;int o=l+r>>1;
    std::nth_element(p+l,p+o,p+r+1);
    t[o].x[0]=t[o].x[1]=t[o].d[0]=p[o].d[0];
    t[o].y[0]=t[o].y[1]=t[o].d[1]=p[o].d[1];
    t[o].z[0]=t[o].z[1]=t[o].d[2]=p[o].d[2];
    if(l<o)ls=bt(l,o-1,(d+1)%3),mt(o,ls);
    if(o<r)rs=bt(o+1,r,(d+1)%3),mt(o,rs);
    return o;
}
#define max(a,b) (a>b?a:b)
#define sqr(x) (1LL*(x)*(x))
#define mind(o) (sqr(max(max(t[o].x[0]-x,x-t[o].x[1]),0))+sqr(max(max(t[o].y[0]-y,y-t[o].y[1]),0))+sqr(max(max(t[o].z[0]-z,z-t[o].z[1]),0)))
#define dis(o) (sqr(x-t[o].d[0])+sqr(y-t[o].d[1])+sqr(z-t[o].d[2]))
void query(int o){
    if(mind(o)>max)return;
    long long tmp=dis(o);
    if(tmp<max&&tmp!=0)max=tmp,cnt=1;
    else if(tmp==max)cnt++;
    if(ls)query(ls);
    if(rs)query(rs);
}
int main(){
    scanf("%d%d%lld",&n,&range,&seed);
    for(i=1;i<=n;i++)p[i]=(P){rand(),rand(),rand()};
    std::sort(p+1,p+1+n,cmp);
    n=std::unique(p+1,p+1+n)-p-1;
    rt=bt(1,n,0);max=1LL<<62;
    for(i=1;i<=n;i++)x=p[i].d[0],y=p[i].d[1],z=p[i].d[2],query(rt);
    printf("%lld\n%lld\n",max,cnt>>1);
}

  评论这张
 
阅读(68)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018