ZOJ Problem Set - 3243
Formally, a diamond with radius r, centered at (x,y), is the set of points whose manhattan distance to (x,y) is no more than r. Given n points p1, p2, ..., pn on the plane, your task is to draw n diamonds, so that pi lies in the interior or on the border of the i-th diamond, and each diamond, except the first one, encloses the previous one.
InputThe first line contains a single integer T (T <= 50), the number of test cases. Each case begins with a single integers n (1 <= n <= 200), the number of diamonds. Each of the following n lines contains three integers x, y, r (1 <= x, y <= 100000, 1 <= r <= 10000), indicating that the i-th diamond should cover (x,y), with radius r.
OutputFor each test case, print the case number in the first line. Each of the following n lines contains two integers x, y, indicating the i-th diamond is centered at (x,y). If there is more than one solution, any one will do. Every test case is solvable.
2 1 1 1 1 2 1 1 1 4 1 2
Case 1: 1 1 Case 2: 1 1 2 1
Author: Liu, Rujia
Source: The 2009 ACM-ICPC Asia Ningbo Regional Online Contest