CF1192A Building Skyscrapers
题目描述
我们要建造一个新的城市:Metropolis。它要建在一个无限大的平面直角坐标系中。建好的城市中应该有 $n$ 座摩天大楼,并且它们所占的(平面直角坐标系中的最小)网格互不相同。在建造的任何时间内,我们定义其上没有摩天大楼的网格**为空**。
给定这 $n$ 座摩天大楼的坐标,请你找出**同时满足下列条件**的建造方法:
- 工程队只有一台起重机,所以同一时刻**最多只能建造一栋楼**。
- 你可以任意指定第一个建造的楼。
- 后建的楼必须与之前建的楼**共一个边或角**。
- 整个建造过程中,必须有一条路径从城外通向正在建造的楼。路径只能经过**空网格**,且只能从一个网格连向**边相邻**的网格。
如果有解,令建造顺序为 $s_1,...,s_n$,其中每一个元素为对应的大楼**编号**。共有两种类别的任务:
1. 你可以输出任何解。
2. 输出令 $s_n,...,s_1$ 这个序列字典序最大的解。
接下来 $n$ 行每行两个整数 $r_i,c_i\in[-10^9,10^9]$,分别为**编号为 $i$ **的摩天大楼所在网格的横坐标和纵坐标。
输入格式
无
输出格式
无
说明/提示
In the first example, there are three skyscrapers in a row. All of them can always be reached from outside the Metropolis, and there are four build orders which preserve connectivity:
- 1, 2, 3
- 2, 1, 3
- 2, 3, 1
- 3, 2, 1
Since $ t = 2 $ , we must choose the first option.
In the second example, the only difference from the first example is that skyscraper 2 shares only corners with skyscrapers 1 and 3, the same set of orders as in the first sample is valid. Since $ t = 1 $ , each of these answers is correct.
In the third example, the Metropolis is disconnected. We obviously can't build that.