#lydlx06x0B16dc. 排版幻灯片 Sorting Slides

排版幻灯片 Sorting Slides

题目描述

一些透明的幻灯片重叠在了一起,每个幻灯片上都标着它的顺序编号。

由于它们是透明的,所以无法看清每个数字究竟标在哪个幻灯片上。

虽然我们无法直接看出每个幻灯片的具体编号,但是却可以根据推理判断出每个幻灯片的编号。

例如上图中,幻灯片被标记为 A,B,C,D,其中 A 的编号为 4,B 的编号为 1,C 的编号为 2,D 的编号为 3。

现在你需要编写一个程序,实现对幻灯片编号的判断。

输入格式

输入包含多组测试数据。

每组测试数据第一行包含整数 nn,表示共有 nn 张幻灯片。

接下来 nn 行,每行包含四个整数 xmin,xmax,ymin,ymaxx_{\min},x_{\max},y_{\min},y_{\max},每个都是幻灯片的边界坐标,幻灯片按输入顺序标记为 A,B,C…(即第一张为 A,第二张为 B,依此类推)。

再接下来 nn 行,每行包含两个整数,第 ii 行的整数表示编号 ii 的横纵坐标。

当输入一行为 00 时,表示输入终止。

输出格式

对于每组数据,第一行输出 Heap x,其中 xx 为数据编号,从 11 开始。

第二行输出每个幻灯片以及其对应的编号,形如 (A,4),不同幻灯片输出之间用空格隔开。

如果无法判断,则输出 none

每组数据输出结束后,输出一个空行。

样例

输入样例:

4
6 22 10 20
4 18 6 16
8 20 2 18
10 24 4 8
9 15
19 17
11 7
21 11
2
0 2 0 2
0 2 0 2
1 1
1 1
0

输出样例:

Heap 1
(A,4) (B,1) (C,2) (D,3)

Heap 2
none

样例解释

第一个数据
幻灯片坐标范围:
A: x∈[6,22], y∈[10,20]
B: x∈[4,18], y∈[6,16]
C: x∈[8,20], y∈[2,18]
D: x∈[10,24], y∈[4,8]

编号坐标:
1: (9,15) 在 A 和 B 内
2: (19,17) 在 A 和 C 内
3: (11,7) 在 D 内
4: (21,11) 在 A 和 D 内

通过推理可得:
A→4, B→1, C→2, D→3

第二个数据
两个幻灯片范围完全相同,两个编号点坐标完全相同,无法唯一确定匹配,输出 none

数据范围

  • 1n261 \leq n \leq 26
  • 坐标可以取负值

时空限制

  • 时间限制:1 秒
  • 空间限制:64 MB