回分類題庫
d138: 資料結構98程式5.1
出處:

Difficulity : N/A
Accepted : 4 Times | Submit :249 Times | Clicks : 1486
Accepted : 3 Users | Submit : 64 Users | Accepted rate : 5%
Time Limit :2001 ms | Memory Limit : 32001 KBytes
題目加入時間 : 2009-12-16 09:50

Content :

Keroro 地理查詢系統2.0


「宇宙侵略軍特殊先鋒部隊」由 Keroro 軍曹領軍,潛入愛爾普藍星。Keroro 的任務在蒐集愛爾普藍星
上重要城市的資訊,包括其經緯度、面積及人口。為了查詢方便,Keroro 已經開發了一個地理資訊查詢
系統。經過一段時間後,Keroro 決定將此系統升級為2.0 版。
2.0 版與1.0 版的差異在於區域搜尋的功能。除了原本1.0 版的3 個查詢功能之外,2.0 版提供了查詢給
定城市的附近城市之功能。以圖一為例,如果Keroro 想查詢城市F 左右各30 度、上下各50 度這區域
內的重要城市,因為F 位於東經125 度北緯10 度,因此相當於查詢東經95 度~東經155 度,南緯40 度
~北緯60 度這區域之內(圖二的虛線)的城市。系統將利用Kero-Tree 快速地找出B 與F 這兩個城市。這
個範例中,Kero-Tree 只需先後比對三個節點:記錄城市A 的節點、記錄城市B 的節點及記錄城市F 的
節點。
請修改以 Pointer implement 的1.0 版,增加區域搜尋的功能。

Input :

輸入除了1.0 版三種指令外,還新增一種指令:第四種指令R 查詢給定城市的附近城市。
R 指令只有一行,其格式共有四個欄位,欄位間以一個空白隔開。
i. 第一個欄位為英文大寫字母 R
ii. 第二個欄位為 15 個字元的字串,代表給定城市的名稱
iii. 第三個欄位為 0~180 之間的整數,代表左右的寬度。例如60 代表給定城市經度的左邊60度及右邊60度之區間。
iv. 第四個欄位為 0~90 之間的整數,代表上下的寬度。例如60 代表給定城市緯度的上方60度及下方60度之區間。

Output :

針對第四種輸入的指令,所對應的輸出為五個欄位,欄位間以一個空白隔開。
i. 第一個欄位為 15 個字元的字串,代表給定城市的名稱
ii. 第二個欄位為-179~179 間且包含一位小數的數字,代表給定城市的經度
iii. 第三個欄位為-89~89 間且包含一位小數的數字,代表給定城市的緯度
iv. 第四個欄位為整數,代表在查詢區域內的城市個數(包括給定的城市)
v. 第五個欄位為整數,代表 Kero-Tree 處理此查詢所需比較的節點個數

Sample Input :

I A               90.0 -45.0 2608186 271.8
I E               30.0 -60.0 1527142 153.6
Q 2.2 48.5
I B               150.0 30.0 1469350 827.9
I D               60.0 -15.0 18884600 6340.5
I G               -90.0 30.0 2203817 105.4
I K               -140.0 20.0 8363710 1214.4
I F               125.0 10.0 1000000 1000.0
I C               140.0 -65.0 4399722 12144.6
R F               30 50
I J               -110.0 65.0 7556900 1579.0
Q 150.0 30.0
I I               -30.0 45.0 3415742 892.0
I L               10.0 70.0 10524400 1081.0
Q 100.0 100.0
I H               10.0 -70.0 11037593 1522.9
Q 10.0 70.0
Q -90.0 30.0
R I               90 30
E

Sample Output :

OK A               1
OK E               2
NO
OK B               2
OK D               2
OK G               3
OK K               4
OK F               3
OK C               2
F               125.0 10.0 2 3
OK J               4
B               1469350 827.9 2
OK I               4
OK L               5
NO
OK H               3
L               10524400 1081.0 5
G               2203817 105.4 3
I               -30.0 45.0 4 7
BYE

Hint :


  

Author :


  Solve it!   Status Forum (0)

C++
C
JAVA
沒有解題記錄 57301. ag100 (4 ms , 318KB)
57273. ag100 (4 ms , 314KB)
49517. acfl (6 ms , 346KB)
27766. henryokc (8 ms , 334KB)
沒有解題記錄

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