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.