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单调递增


题目来源

没有写明来源

加入题单

上一题 下一题 算法标签: