AdditionalFile5629.zip

#5629. 「POI2026 R2」Spotkanie na Bajhattanie

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

题目译自 XXXIII Olimpiada Informatyczna – II etap Spotkanie na Bajhattanie

一些中层商务人士想在 Bajhattan 组织一场聚会。Bajhattan 的地图类似于一个无限大的二维网格，其中大街对应于 $x=a$（$a$ 为整数）的垂直直线，街道对应于 $y=b$（$b$ 为整数）的水平直线。每一条大街与街道相交，形成坐标为 $(a, b)$ 的交叉口。从坐标为 $(a, b)$ 的交叉口出发，恰好需要一分钟可以移动到坐标为 $(a \pm 1, b)$ 或 $(a, b \pm 1)$ 的相邻交叉口。

共有 $n$ 名商务人士，编号从 $1$ 到 $n$。聚会开始前，第 $i$ $(1 \leq i \leq n)$ 名商务人士住在位于坐标为 $(x_{i}, y_{i})$ 的交叉口处的酒店里。

这些商务人士希望尽快在某个交叉口会面。一旦确定了聚会地点，所有人将同时从各自的酒店出发，沿着最短路径前往该地点。众所周知，让大家等最后一个人是很尴尬的，甚至等最后两三个也是如此。因此，你被要求对于 $1$ 到 $n$ 之间的每一个整数 $k$，找到一个交叉口 $(x, y)$，使得如果在此交叉口组织聚会，恰好会有 $k$ 名商务人士在所有人中最后到达；如果不存在这样的交叉口，则说明无解。换句话说，我们希望恰好有 $k$ 名商务人士在同一时刻最后出现在聚会上。

输入格式

输入第一行包含一个整数 $n$ $(1 \leq n \leq 10^{6})$，表示商务人士的数量。

接下来的 $n$ 行描述了他们的住宿地点。其中第 $i$ $(1 \leq i \leq n)$ 行包含两个整数 $x_{i}, y_{i}$ $(-10^{9} \leq x_{i}, y_{i} \leq 10^{9})$，描述第 $i$ 名商务人士所住酒店的坐标。同一个酒店可能住有多名商务人士。

输出格式

应输出 $n$ 行。在第 $k$ $(1 \leq k \leq n)$ 行中，应包含两个整数 $a_{k}, b_{k}$ $(-10^{18} \leq a_{k}, b_{k} \leq 10^{18})$，表示如果聚会在交叉口 $(a_{k}, b_{k})$ 组织，则恰好有 $k$ 名商务人士最后到达；如果不存在这样的交叉口，则输出 NIE。如果存在多个符合条件的交叉口，输出其中任意一个即可。

样例 1

输入

5
-1 0
3 0
-2 -1
1 2
1 -1

输出

1 0
0 -1
0 0
1 -1
NIE

下图展示了 $k=3$ 时最迟到达的商务人士的示例路径。

样例 2

输入

3
0 3
0 3
1 1

输出

0 2
1 1
NIE

附加样例

1. $n=42$，第 $i$ 名商务人士住在坐标为 $x_{i}=i, y_{i}=i+(i \bmod 3)$ 的酒店。
2. $n=10 \cdot 101^{2}=102010$，在每个满足 $|x|,|y| \leq 50$ 的交叉口 $(x, y)$ 处都恰好住有十名商务人士。
3. $n=3$，酒店分别位于点 $(10^{9}, 10^{9}), (-10^{9}, 10^{9}), (-10^{9}, -10^{9})$。
4. $n=4 \cdot 10^{4}$，第 $i$ 名商务人士住在坐标为 $x_{i}=i \cdot 10^{4}, y_{i}=i \cdot(-1)^{i} \cdot 10^{4}$ 的酒店。
5. $n=10^{6}$，每家酒店都位于方程形式为 $y= \pm x \pm 10^{9}$ 的四条直线之一。

数据范围与提示

详细子任务附加限制及分值如下表所示。