回分類題庫
d017: 2006 程式達人 H - 幻燈片排序
出處:

Difficulity : 2
Accepted : 8 Times | Submit :86 Times | Clicks : 1964
Accepted : 4 Users | Submit : 10 Users | Accepted rate : 40%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2008-10-10 08:47

Content :

岸和田博士即將在今天下午有場重要的演講。但很不幸的,博士並不是一個井然有序的人,他總是將他要用的幻燈片堆成一團,而且每張幻燈片的大小還不一樣。所以在今天演講前,博士必須要將幻燈片排好。可是博士又相當的懶惰,他希望能夠花最少的工夫將幻燈片排序。

而目前的情況是這樣的:所有的幻燈片接依照演講的順序,再幻燈片的某個地方會標有一號碼,但是因為換燈片是透明的,所以我們無法明確的知道到底每個號碼是在哪一張幻燈片上。雖然如此,但是我們可以透過推論得知數字到底是數字是標在哪張幻燈片上。例如上面的圖,我們可以推論出 D 的號碼是 3,B 的號碼是 1,C 的號碼是 2,而 A 的號碼是 4。

你現在的任務是要寫一支程式,將上述的程序自動化。

Input :

輸入檔中包含了數組幻燈片堆的描述。每一個幻燈片堆描述的第一行是一個單一的整數 n,代表這一堆有多少張投影片。接下來會有 n 行,每一行包含了四個整數 Xmin, Xmax, Ymin, Ymax,由這四個數字可以表達幻燈片四個角的座標。而依照輸入的順序,每張幻燈片依序標著 A, B, C, …。

接下來還會有 n 行輸入,每行包含了兩個整數,依序 (1, 2, …, n) 代表每個號碼的 (x, y) 座標。你可以假設沒有任何一個號碼會出現在幻燈片的邊界上。

最後,若輸入檔的幻燈片以 0 為開頭,則程式中止。

Output :

首先以每筆測試資料的輸入順序印出其號碼(Heap x)。接著依照幻燈片所標的英文字母順序,將有辦法”確認”其號碼的投影片印出來。注意,不見得有辦法推論出所有投影片的號碼。

如果無法推論出任何換燈片的號碼,則印出 none。每筆測試資料的輸出以一空白行作為結尾。

Sample Input :

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

Sample Output :

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

Heap 2
none

Hint :

題目原出處:ACMOJ 663

Author :

(管理員:MrWrongAnswer)

  Solve it!   Status Forum (2)

C++
C
JAVA
44761. justin6 (6 ms , 408KB)
44708. justin5 (8 ms , 402KB)
55486. ag100 (4 ms , 300KB)
55483. ag100 (4 ms , 300KB)
55482. ag100 (6 ms , 302KB)
55485. ag100 (8 ms , 300KB)
55484. ag100 (10 ms , 294KB)
沒有解題記錄

執行時間會受很多因素影響因此僅供參考,主機等級請看這裡