回分類題庫
d012: 98年台中區第二題
關鍵字: 98年台中區複賽

測資點 : 4 | Time Limit : 1000 ms | Memory Limit : 32000 KB
Accepted : 187 Times / 173 Users | Submit : 274 Times / 179 Users | Accepted rate : 97%
題目加入時間 : 2011-09-10 12:06

Content: 简体中文

二度空間上的排名計算問題(2D rank finding problem):給定二度平面空間(2D)上的點A = (a1,a2)與點B = (b1,b2),其大小關係定義為若A > B 若且唯若 a1> b1 且 a2 > b2 ;亦即A點在B點的右上方。如下圖中,B >A, C>A, D>A, D>C, D> B。值得注意的是,並非任意兩點均可以決定大小關係,如下圖中的點A與點E,點D與點E等,無法決定這兩點的大小關係故為無法比較(incomparable)。給定N個點(x1,y1), (x2,y2), …, (xn,yn),定義某一個點的排名(rank) 為所給的點集合中,比該點小的點的個數。

 

如上圖中,rank(A)= 0, rank(B) = 1, rank(C) = 1, rank(D) = 3, rank(E) = 0。設計一個程式,讀取點的名稱與座標,計算出在所給定的集合中,所有點的排名值。 

Input:

第一行有一個正整數 N 代表點的個數,接下來有 N 行資料,每行第一個字母為點的名稱(如 A, B, …, Z),其後之兩個實數分別為該點的x座標與y座標。

Output:

請依照下面輸出範例的格式,輸出這 N 個點的排名值。

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
5
A 3.0 2.0
B 2.3 1.2
C 5.1 0.3
D 6.1 0.9
E 3.5 9.1

Sample Output :

A 1
B 0
C 0
D 1
E 2

Hint :

註:原題目只有一組輸入檔資料,本系統第二組以後的資料由本站管理員自己產生,如有錯誤請指正。

Author :

98年台中區複賽 (管理員:sagit)

  Solve it!   Status Forum