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

n+e

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

 
 
 

日志

 
 

[BZOJ3815]卡常数  

2015-05-18 11:07:59|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3815: 卡常数

Time Limit: 50 Sec  Memory Limit: 512 MB
Submit: 12  Solved: 10
[Submit][Status][Discuss]

Description

在某个诡异的地方,有一座智慧之城,那里的人民平均智商为 192,智商低于 150 的人都被称为弱智。智慧之城的市长名叫卡常(Karp-de-Chant),他 12 岁时在智慧之城中心大学 Cross Institute 获得博士学位,两年后发明了一种数列 —— 卡常数(Karp-de-Chant Number),该数列可用来解决或优化数论、图论等领域的多种经典难题。后来,卡常数被 Trajan(智慧之城的副市长)用 spaly 树进行扩展后,威力大大增加,可以在线性时间内解决各种网络流问题和其它一些难题。卡常和 Trajan 因此分别被选为正、副市长,他们和智慧之城内的另一些智者一起,领导人民共同建设人类智慧,发挥创造和改进的能力。
然而某一天,智慧之城突然受到了反人类智慧者的袭击,反人类智慧者在城内设置了 N 个摄像头(由于他们的智商很低,只会用摄像头这种垃圾玩意),企图监视城内的人们。卡常、Trajan 决定找到这些摄像头并摧毁它们。
智慧之城里有一个用扩展卡常数原理设计的发射器,将其放在合适位置并设置半径以后,所有位于球心为这个发射器的位置、半径为指定值的球面上的目标都能被发现。在卡常、Trajan 的带领下,智慧之城的人们用这个发射器进行了若干次实验,并发现了一些摄像头的位置。比较囧的是,每次发射都能且仅能发现一个摄像头,但是,反馈回来的结果貌似有些不对劲……
后来人们终于找到了这 N 个摄像头的位置,并发现在他们用发射器进行实验的过程中,某些摄像头被移位——这就是导致反馈结果不对劲的原因。但是,在对实验结果进行分析的时候,人们却肿么也回忆不起每次实验发现的摄像头是哪个了(可能是遭遇了灵异事件导致脑抽),只知道每次实验时发射器的位置和半径。你的任务就是,根据实验数据(为了防止被反人类智慧者窃取,已经进行了加密)找出每次实验时被发射器找到的摄像头的编号。

Input

第一行两个正整数 N、M,表示摄像头数量(摄像头以 1 到 N 编号)和事件数量。
第二行两个实数 a、b,表示加密参数。
接下来 N 行,每行三个实数 (x,y,z),表示 1 到 N 号摄像头的初始位置坐标。
接下来 M 行,每行描述一个事件,有两种可能的事件(保证其中实数的精度充分高):
0 i x y z,表示将编号为 i 的摄像头的坐标改为 (x,y,z);
1 x y z r,表示进行一次实验,将发射器放在 (x,y,z) 处并设置半径为r,数据保证每次实验能且仅能发现一个摄像头;
加密方式:设函数 f(x)=ax?bsinx,对于所有事件中的参数(i、x、y、z、r),均加密成 f(last_res×原值+1),其中 last_res 为上一个实验事件的返回值(即发现的摄像头编号),若之前未进行过实验则 last_res=0.1。

Output

对于每个实验事件,输出发现的摄像头编号,一个一行。

Sample Input

6 10 1 0 -3.6 7.2 3.6 9.7 0.4 0.5 8.8 -4.7 0.5 9.6 8.2 -5.7 0.3 -9.9 1.5 0.5 -5.7 -1.0 0 1.3 1.92 0.13 1.85 1 1.98 1.55 1.2 2.360183811 1 8.2 0.9 2.1 9.981091248 1 -7.4 -44.0 11.2 83.061927835 1 20.8 -9.6 -11.8 31.598039153 0 10.0 11.2 -19.73 -19.1 0 13.0 7.3 28.6 22.6 0 4.0 22.3 -17.6 1.3 1 -3.2 -14.0 16.6 30.9549661993 0 7.0 -3.1 5.8 -0.9

Sample Output

1 6 2 3 1

HINT

N<=65536
M<=65536
所有的测试点满足 0≤b<a<5,坐标的绝对值均不超过 100,所有坐标均为随机生成且至少精确到 10^?5。
为尽可能减小精度误差,建议 C/C++ 使用long double类型、Pascal 使用 EXTENDED 类型存储实数。

Source

Solution

发现一道kdtree。结果坑点:
1.强制在线不能用牛顿迭代解方程好像精度不够;
2.信息维护龊了好像会退化

Code

/**************************************************************
    Problem: 3815
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:27364 ms
    Memory:14872 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#include<algorithm>
typedef double ld;
#define N 66666
#define eps 1e-6
int rt,n,m,i,to[N],fa[N<<1],D,bb;ld a,b,ans=0.1,x,y,z,r,aa,ee;
#define isd(c) (c>='0'&&c<='9')
char ch,op;ld F(){
    while(ch=getchar(),!isd(ch)&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1);
    while(ch=getchar(),isd(ch))aa=aa*10+ch-'0';ee=1;
    if(ch=='.')while(ch=getchar(),isd(ch))aa+=(ch-'0')*(ee*=0.1);return bb?aa:-aa;
}
ld G(ld l=-100,ld r=100){
    ld y=F(),mid,x;
    while(r-l>1e-9){
        x=(mid=(l+r)*0.5)*ans+1;
        if(a*x-b*sin(x)<y)l=mid;
        else r=mid;
    }
    return (l+r)*0.5;
}
struct P{ld d[3];int n;}p[N];
inline bool operator<(const P&a,const P&b){return a.d[D]<b.d[D];}
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define cmax(a,b) (a<b?a=b:1)
#define cmin(a,b) (a>b?a=b:1)
struct T{
    ld d[3],x[2],y[2],z[2];int s[2],flag,id;
    void setup(ld xx,ld yy,ld zz){
        x[0]=x[1]=d[0]=xx,y[0]=y[1]=d[1]=yy,z[0]=z[1]=d[2]=zz;
    }
}t[N<<1];
#define ls t[o].s[0]
#define rs t[o].s[1]
void mt(int o){
    t[o].x[0]=min(t[ls].x[0],t[rs].x[0]),t[o].x[1]=max(t[ls].x[1],t[rs].x[1]),
    t[o].y[0]=min(t[ls].y[0],t[rs].y[0]),t[o].y[1]=max(t[ls].y[1],t[rs].y[1]),
    t[o].z[0]=min(t[ls].z[0],t[rs].z[0]),t[o].z[1]=max(t[ls].z[1],t[rs].z[1]);
    if(t[o].flag==0)
        cmin(t[o].x[0],t[o].d[0]),cmax(t[o].x[1],t[o].d[0]),
        cmin(t[o].y[0],t[o].d[1]),cmax(t[o].y[1],t[o].d[1]),
        cmin(t[o].z[0],t[o].d[2]),cmax(t[o].z[1],t[o].d[2]);
}
int bt(int l,int r,int d){
    int o=l+r>>1;D=d;
    std::nth_element(p+l,p+o,p+r+1);to[p[o].n]=o,t[o].id=p[o].n;
    t[o].setup(p[o].d[0],p[o].d[1],p[o].d[2]);
    if(l<o)ls=bt(l,o-1,(d+1)%3),fa[ls]=o;
    if(o<r)rs=bt(o+1,r,(d+1)%3),fa[rs]=o;
    return mt(o),o;
}
#define abs(x) (x>0?x:-(x))
#define sqr(x) ((x)*(x))
#define dis(o) (sqr(t[o].d[0]-x)+sqr(t[o].d[1]-y)+sqr(t[o].d[2]-z))
#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 maxd(o) (max(sqr(t[o].x[0]-x),sqr(x-t[o].x[1]))+max(sqr(t[o].y[0]-y),sqr(y-t[o].y[1]))+max(sqr(t[o].z[0]-z),sqr(z-t[o].z[1])))
int query(int o){
    if(mind(o)>r+eps||maxd(o)<r-eps)return 0;
    if(t[o].flag==0&&abs(dis(o)-r)<=eps)return t[o].id;int tmp=0;
    if(ls&&(tmp=query(ls)))return tmp;
    if(rs&&(tmp=query(rs)))return tmp;
    return 0;
}
int main(){
    scanf("%d%d",&n,&m);t[0].x[0]=t[0].y[0]=t[0].z[0]=1e10,t[0].x[1]=t[0].y[1]=t[0].z[1]=-1e10;
    for(a=F(),b=F(),i=1;i<=n;i++)p[i]=(P){F(),F(),F(),i};rt=bt(1,n,0);
    for(;m--;){
        while(op=getchar(),!isd(op));
        if(op=='0'){
            i=int(G(1,n)+0.5),x=G(),y=G(),z=G(),t[++n].setup(x,y,z);t[to[i]].flag=1;
            for(int k=to[i];k;k=fa[k])mt(k);to[i]=n;t[n].id=i;D=0;
            for(int k=rt;k;D=(D+1)%3){
                int&nxt=t[k].s[t[k].d[D]<=t[n].d[D]];
                if(!nxt){fa[n]=k,nxt=n;break;}else k=nxt;
            }
            for(int k=fa[n];k;k=fa[k])mt(k);
        }
        else{
            x=G(),y=G(),z=G(),r=G(0,350);r=sqr(r);
            printf("%.0lf\n",ans=query(rt));
        }
    }
}
  评论这张
 
阅读(245)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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