Logo Universal Online Judge

UOJ

时间限制:1 s 空间限制:32 MB

#196. 栓狗方案

统计

【问题描述】
一个公园由2000000条垂直方向的道路与2000000条水平方向的道路围成栅格状,相邻两条平行道路间的距离为1,两个方向的道路均从1到2000000进行编号,每个栅格(面积为1平方)中都栽有一棵树。
现在公园里有N只小狗在玩耍,它们的编号为1到N。每一只小狗都套着一根固定长度的链索,并且每一只狗都有一棵特别喜欢的树,小狗总是在路上散步,且链索总是拖在道路上,而不会拖到栅格中去。
现在要把所有的小狗都栓到树上,一棵树上可以拴任意多条小狗,但拴狗方案必须满足以下条件:
(1)每只小狗都能散步到达它最喜欢的树下。
(2)无论编号小的小狗溜达到什么地方,编号大的小狗都能到达该地方,即任意一个编号小的小狗的活动范围必须包含在编号比它大的小狗的活动范围之内。
请您编一程序为每一只小狗找一棵栓住它的树使得上述条件均能得到满足。
【输入】
输入文件的第一行包含一个整数N(1≤N≤100000),表示小狗的数量。
接下来的N行每行包含一只小狗的信息,第I+1行表示第I只小狗的信息,每行数据的格式如下:
R S D
表示这只小狗最喜欢的树位于第R行第S列,D为栓这只小狗的链索的长度,D不大于1000000。
【输出】
输出文件包含N行,第I行包含一对用空格隔开的整数表示用来栓第I只小狗的树的坐标。第一坐标表示行,第二坐标表示列,对每一组输入数据问题保证有解,但不一定唯一。

【样例】
    输入:                                         输出:
    6                                               20 27
    21 27 1                                         20 27
    23 27 3                                         19 28
    19 27 5                                         19 29
    21 33 6                                         19 29
    23 29 6                                         19 30
    26 30 7

【注释】
小狗从栓它的树到喜欢的树之间的距离为两树横坐标之差的绝对值从加上纵坐标之差的绝对值。树的坐标用它的左下角的道路交叉点的坐标表示。