CF575E.Spectator Riots

It’s riot time on football stadium Ramacana! Raging fans have entered the field and the police find themselves in a difficult situation. The field can be represented as a square in the coordinate system defined by two diagonal vertices in (0,0) and (105, 105). The sides of that square are also considered to be inside the field, everything else is outside.

In the beginning, there are N fans on the field. For each fan we are given his speed, an integer v__i as well as his integer coordinates (x__i, y__i). A fan with those coordinates might move and after one second he might be at any point (x__i + p, y__i + q) where 0 ≤ |p| + |q| ≤ v__i. p, q are both integers.

Points that go outside of the square that represents the field are excluded and all others have equal probability of being the location of that specific fan after one second.

Andrej, a young and promising police officer, has sent a flying drone to take a photo of the riot from above. The drone’s camera works like this:

1. It selects three points with integer coordinates such that there is a chance of a fan appearing there after one second. They must not be collinear or the camera won’t work. It is guaranteed that not all of the initial positions of fans will be on the same line.
2. Camera focuses those points and creates a circle that passes through those three points. A photo is taken after one second (one second after the initial state).
3. Everything that is on the circle or inside it at the moment of taking the photo (one second after focusing the points) will be on the photo.

Your goal is to select those three points so that the expected number of fans seen on the photo is maximized. If there are more such selections, select those three points that give the circle with largest radius among them. If there are still more suitable selections, any one of them will be accepted. If your answer follows conditions above and radius of circle you return is smaller then the optimal one by 0.01, your output will be considered as correct.

No test will have optimal radius bigger than 1010.

足球场“拉马卡纳”（Ramacana）上正爆发骚乱！狂怒的球迷已冲入球场，警方陷入了困境。球场可表示为坐标系中一个正方形区域，其两条对角顶点分别为 $(0,0)$ 和 $(10^5, 10^5)$。该正方形的四条边也被视为球场内部，其余所有区域均属场外。

初始时刻，球场上有 $N$ 名球迷。对每位球迷，我们给出其速度（整数）$v_i$ 及其整数坐标 $(x_i, y_i)$。一名位于 $(x_i, y_i)$ 的球迷可以移动；一秒钟后，他可能出现在任意一点 $(x_i + p, y_i + q)$，其中满足 $0 \le |p| + |q| \le v_i$，且 $p, q$ 均为整数。

所有超出上述正方形区域的点均被排除；其余所有合法点对该球迷而言，在一秒钟后出现的概率均相等。

安德烈（Andrej），一位年轻而富有潜力的警官，派出一架无人机从空中拍摄骚乱现场。该无人机的相机工作方式如下：

1. 相机选取三个具有整数坐标的点，要求这三个点在一秒后均有可能出现球迷（即每个点均是至少一名球迷在一秒后可能到达的位置）。这三个点不能共线，否则相机无法工作。题目保证：初始时所有球迷的位置不全在同一条直线上。
2. 相机聚焦于这三个点，并生成一个唯一通过这三点的圆。照片在一秒钟后（即初始状态之后一秒钟）拍摄。
3. 在拍照瞬间（即聚焦三点后一秒钟），所有位于该圆上或圆内的物体都将被摄入照片。

你的目标是选择这三个点，使得照片中期望出现的球迷人数最大化。若存在多个这样的三元组，则在其中选择所确定圆的半径最大者。若仍存在多个满足条件的三元组，则任选其一即可。若你的答案满足上述条件，且你返回的圆半径与最优半径之差小于 $0.01$，则你的输出将被视为正确。

任何测试用例的最优半径均不会超过 $10^{10}$。

The first line contains the number of fans on the field, N. The next N lines contain three integers: x__i ,y__i, v__i. They are the x-coordinate, y-coordinate and speed of fan i at the beginning of the one second interval considered in the task.

• 3 ≤ N ≤ 105
• 0 ≤ x__i, y__i ≤ 105
• 0 ≤ v__i ≤ 1000
• All numbers are integers

第一行包含场上的球迷数量 $N$。接下来的 $N$ 行每行包含三个整数：$x_i$、$y_i$、$v_i$，分别表示第 $i$ 位球迷在本题所考虑的 1 秒时间区间起始时刻的 $x$ 坐标、$y$ 坐标和速度。

• $3 \leq N \leq 10^5$
• $0 \leq x_i, y_i \leq 10^5$
• $0 \leq v_i \leq 1000$
• 所有数字均为整数

You need to output the three points that camera needs to select. Print them in three lines, with every line containing the x-coordinate, then y-coordinate, separated by a single space. The order of points does not matter.

你需要输出相机需要选择的三个点。将它们打印在三行中，每行包含 x 坐标和 y 坐标，用一个空格分隔。点的顺序无关紧要。