CF575E Spectator Riots

拉马卡纳足球场上发生了骚乱！愤怒的球迷们冲进了球场，警方陷入了困境。球场在平面直角坐标系中可表示为一个正方形，对角线的两个顶点坐标为 $(0,0)$ 和 $(10^{5},10^{5})$。这个正方形的边界也算作球场内部，其它所有区域都属于球场外部。 一开始，球场内共有 $N$ 位球迷。每个球迷的信息包括一个速度（整数 $v_{i}$）以及其初始坐标（整数 $x_{i},y_{i}$）。某一球迷在原坐标后，可以移动到任意符合 $0 \leq |p|+|q| \leq v_{i}$ 的整数点 $(x_{i}+p, y_{i}+q)$。$p$、$q$ 均为整数。 超出正方形边界的位置不计入，其他点都有相同概率成为该球迷一秒后的位置。 安德烈，一名年轻有为的警察，派出了无人机从空中拍摄骚乱。无人机的相机规则如下： 1. 选择三个整数坐标的点，这些点必须是一秒后某球迷有可能到达的位置。所选三点不共线，否则相机无法工作。保证所有球迷的初始位置并非都共线。 2. 相机对准这三点，建立一个通过这三点的圆。拍照发生在对准后一秒（即初始时刻后一秒）。 3. 拍照时，所有在该圆上及以内的球迷都会被拍到。 你的任务是选择这三个点，使得期望被拍到的球迷数最大。如果存在多种选择，选择半径最大的圆。如果还有多种选择，任选一种输出即可。如果你选择的圆的半径与最优半径的差值小于 $0.01$，则输出也视为正确。 保证没有测试点的最优半径超过 $10^{10}$。

第一行一个整数 $N$，表示球迷数量。接下来的 $N$ 行，每行三个整数，分别为球迷的 $x_i$ 坐标、$y_i$ 坐标和速度 $v_i$，均为初始时刻的数据。 - $3 \leq N \leq 10^{5}$ - $0 \leq x_i, y_i \leq 10^{5}$ - $0 \leq v_i \leq 1000$ - 所有数字均为整数

你需要输出相机需要选择的三个点。每行输出一个点的 $x$ 坐标和 $y$ 坐标，并以一个空格分隔。顺序任意。

由 ChatGPT 5 翻译