P1375. 区间

问题描述

在一个新开张的开发者大楼的地下室天花板上安装了一个光源。不幸的是，覆盖地板的材料对光线非常敏感。经过调查发现，这种材料的预期使用寿命会显著缩短。为了避免这种情况，当局决定通过覆盖的方式来保护对光敏感的区域。解决方案是仅在那些未被管道遮挡的地板部分安装覆盖物。为了处理这种情况，第一个决定是简化实际情况，并在三维空间中构造一个二维模型。

在这个模型中，x 轴与地板的水平面对齐。光源被视为一个具有整数坐标的点光源 [bx, by]。管道用圆表示。第 i 个圆的中心具有整数坐标 [cxi, cyi] 和整数半径 ri。由于管道是实心材料，圆之间不能重叠。管道不会反射光线，光线也无法穿过管道。你需要编写一个程序，确定 x 轴上由于管道遮挡而没有光线到达的非重叠区间。

输入

输入由若干块组成，每块（除了最后一块）描述地下室的一种情况。每块的第一行包含一个正整数 N < 500，表示管道的数量。第二行包含两个整数 bx 和 by，以空格分隔。接下来的 N 行中，每行包含三个整数 cxi, cyi, ri，其中 cyi + ri < by。每行中的整数以空格分隔。最后一块仅包含一行 n = 0。

输出

输出由若干块组成，与输入中的块对应（除了最后一块）。每个块后必须输出一个空行。每个块中的每一行包含两个实数，表示由于管道遮挡而没有光线到达的区间的端点。实数精确到小数点后两位，以空格分隔。区间按照 x 坐标递增的顺序排序。

输入示例 1

6
300 450
70 50 30
120 20 20
270 40 10
250 85 20
220 30 30
380 100 100
1
300 300
300 150 90
1
300 300
390 150 90
0

输出示例 1

0.72 78.86
88.50 133.94
181.04 549.93

75.00 525.00

300.00 862.50

来源

Central Europe 1996

如果需要进一步帮助，请告诉我！