8272: BZOJ4272:physic 物理
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
声波(Sound Wave或Acoustic Wave)是声音的传播形式。声波是一种机械波,由物体(声源)振动产生,声波传播的空间就称为声场。在气体和液体介质中传播时是一种纵波,但在固体介质中传播时可能混有横波。人耳可以听到的声波的频率一般在20赫兹至20000赫兹之间。 不同动物和不同的人能听到的声波频率都不一样。这里就不上图了。 现在,sg在和妹子玩一个很好玩的游戏。 sg站在1号点,后面有他的n-1个小弟。现在妹子想告诉sg一些话,但是她不知道选谁。由于sg的小弟们构造奇特,他们能听到的声波频率也是不一样的。第i个人可以发出并接收声波频率为[xi,yi]的声音,并且每个人的声音最多只能传播不超过l的距离。每一次说话并被另一个人接收到的过程都要消耗1单位时间。 现在给出所有人能发出并接收的声波频率的范围和位置,sg的妹子想知道,每个小弟传话给sg要多久。由于sg很牛逼,他可以接收所有小弟发出的声波,当然前提要在距离之内。sg的位置为0。
输入格式
第一行:n,l,含义见题意。 第二行至第n行:xi,yi,li,[xi,yi]是第i个小弟能发出并接收的声波频率范围,li是第i个小弟的位置。
输出格式
第一行至第n-1行:第i行表示第i+1个小弟要传话给sg所消耗的时间。
样例输入
3 1 1 2 1 2 3 2 1 1 0 0 0 2
样例输出
1 2
提示
对于100%的数据,1≤n≤250000,0≤xi,yi,li≤2000000000,1≤l≤2000000000,xi≤yi。保证li单调递增
题目来源
没有写明来源