回分類題庫
d134: 資料結構98程式4.2 (Linked List)
出處:

Difficulity : 5
Accepted : 85 Times | Submit :207 Times | Clicks : 1251
Accepted : 70 Users | Submit : 87 Users | Accepted rate : 80%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-12-09 09:42

Content :

Keroro 地理查詢系統V1.0


「宇宙侵略軍特殊先鋒部隊」由 Keroro 軍曹領軍,潛入愛爾普藍星。Keroro 的任務在蒐集愛爾普藍星
上重要城市的資訊,包括其經緯度、面積及人口。為了查詢方便,Keroro 開發了一個地理資訊查詢系統。
此系統可以讓Keroro 小隊的成員隨時動態地輸入新發現的城市資訊,也可以隨時根據經緯度來查詢位於
此經緯度的城市相關資訊。
Keroro 因此修改了Binary Search Tree 的結構,研究出Kero-Tree 以快速地處理經緯度的查詢系統。
Kero-Tree 將原本一般Binary Search Tree 的一維資料延伸至二維。與Binary Search Tree 不同,Kero-Tree
的每個節點最多有4 個分支(Branch)。每個節點的Key 記錄了一個城市的經緯度。而且對於Kero-Tree
的每個節點,其
(a) 第一個 Child 的城市,其經度位於其Parent 的西方,其緯度位於其Parent 的南方
(b) 第二個 Child 的城市,其經度位於其Parent 的西方,其緯度位於其Parent 的北方
(c) 第三個 Child 的城市,其經度位於其Parent 的東方,其緯度位於其Parent 的南方
(d) 第四個 Child 的城市,其經度位於其Parent 的東方,其緯度位於其Parent 的北方
圖一所示即為由一個 11 個節點所形成的Kero-Tree。以Root 為例,其記錄了位於東經121 度38 分、北
緯25 度02 分的台北。而其
(a) 第一個 Child 記錄了位於東經120 度16 分、北緯 22 度38 分的高雄,也就是位於台北的西南方。
(b) 第二個 Child 記錄了位於東經121 度29 分、北緯 31 度01 分的上海,也就是位於台北的西北方。
(c) 第三個 Child 記錄了位於東經151 度12 分、南緯 33 度52 分的雪梨,也就是位於台北的東南方。
(d) 第四個 Child 記錄了位於東經135 度46 分、北緯 35 度0 分的京都,也就是位於台北的東北方。
Keroro 若欲查詢經緯度位於西經74 度0 分、北緯40 度43 分的城市,透過圖一的Kero-Tree,只要比較
第一層Root Taipei 的經緯度,接著比較Taipei 西北方的節點Shanghai 的經緯度,再接著比較Shanghai
西北方的節點Paris 的經緯度,最後比較Paris 西南方的節點New York 的經緯度,就可查詢到位於西經
74 度0 分、北緯40 度43 分的城市是New York。
請分別以Array 及Pointer 來Implement Kero-Tree,提供輸入與查詢城市資訊的功能。


Input :

輸入共有三種可能的指令
(1) 第一種指令 I 輸入城市的基本資訊(經緯度、名稱、人口、面積),其格式共有六個欄位,欄位間以一
個空白隔開。
i. 第一個欄位為英文字母大寫 I
ii. 第二行為 15 個字元的字串,記錄城市的名稱。字串中可能有空白(例如:New York)
iii. 第三個欄位為-179~179 間且包含一位小數的數字,代表經度
iv. 第四個欄位為-89~89 間且包含一位小數的數字,代表緯度
v. 第五個欄位為 0~50,000,000 的整數,代表城市的人口。
vi. 第六個欄位為 0~100,00 間包括一位小數的數字,代表城市的面積。
(2) 第二種指令 Q 查詢位於給定經緯度的城市名稱及其相關資訊。Q 指令只有一行,其格式共有三個欄
位,欄位間以一個空白隔開。
i. 第一個欄位是英文大寫字母 Q
ii. 第二個欄位為-179~179 間且包含一位小數的數字,代表查詢的經度
iii. 第三個欄位為-89~89 間且包含一位小數的數字,代表查詢的緯度
(3) 第三種指令 E,代表系統結束。

Output :

針對三種不同的輸入指令,所對應的輸出如下
(1) 若輸入為第一種指令 I,則輸出一行字串,包括三個欄位,欄位間以一個空白隔開。
i. 第一個欄位為兩個英文大寫字母 OK
ii. 第二個欄位為輸入城市的名稱。
iii. 第三個欄位為輸入城市的節點位於 Kero-Tree 的層數(Root 為第1 層)
(2) 若輸入為第二種指令 Q,則輸出查詢結果,包括四個欄位,欄位間以一個空白隔開。
i. 第一個欄位為城市名稱
ii. 第二個欄位為此城市的人口。
iii. 第三個欄位為此城市的面積。
iv. 第四個欄位為此城市的節點位於 Kero-Tree 的層數(Root 為第1 層)
若查詢的位置不存在,則輸出兩個英文大寫字母NO。
* 請注意:有可能查詢當時,Kero-Tree 中尚未輸入所查詢的城市資訊,因此查詢結果為NO。但接
著由於此城市資訊的輸入,因此再度查詢時,查詢結果與前次查詢結果不同,後面的查詢可能因此
可以查詢出城市的相關資訊。
(3) 若輸入為第三種指令 E,則輸出三個英文大寫字母BYE

Sample Input :

I Taipei 121.3 25.2 2608186 271.8
I Kaohsiung 120.1 22.3 1527142 153.6
Q 2.2 48.5
I Kyoto 135.4 35.0 1469350 827.9
I Shanghai 121.2 31.1 18884600 6340.5
I Paris 2.2 48.5 2203817 105.4
I New York -74.0 40.4 8363710 1214.4
I Sydney 151.1 -33.5 4399722 12144.6
I London -0.5 51.4 7556900 1579.0
Q 135.4 35.0
I Berlin 13.2 52.3 3415742 892.0
I Moscow 37.3 55.4 10524400 1081.0
Q 100.0 100.0
I Sao Paulo -46.3 -23.3 11037593 1522.9
Q 37.3 55.4
Q 2.2 48.5
E

Sample Output :

OK Taipei 1
OK Kaohsiung 2
NO
OK Kyoto 2
OK Shanghai 2
OK Paris 3
OK New York 4
OK Sydney 2
OK London 4
Kyoto 1469350 827.9 2
OK Berlin 4
OK Moscow 5
NO
OK Sao Paulo 3
Moscow 10524400 1081.0 5
Paris 2203817 105.4 3
BYE

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
沒有解題記錄 14902. ds97703039 (2 ms , 352KB)
14863. ds96703004 (2 ms , 350KB)
14792. ds96703035 (2 ms , 358KB)
14536. ds97703002 (2 ms , 368KB)
14517. ds96703036 (2 ms , 326KB)
沒有解題記錄

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