b067: 6. 下棋問題
標籤 :
通過比率 : 36人/48人 ( 75% ) [非即時]
評分方式:
Tolerant

最近更新 : 2007-12-08 07:52

內容
eToy 發明了一個新的益智遊戲,該遊戲由A 和B 兩人輪流在一個1,000,000 x 1,000,000 的方格棋盤上的格線交點下棋,格線交點的座標以(x, y), 0 ≤ x , y ≤ 1,000,000 表示之,(0, 0)代表棋盤最左下角那點。
每一個棋子放置的位置不可以與任何其它棋子在同一X 座標或Y 座標上,棋盤上新增加一個棋子時,棋盤上的計數器會自動算出以目前棋盤上棋子所能夠圍成的「無障礙四方形」數。
「無障礙四方形」是指以任意兩個棋子所定義出的四方形內部不含其它棋子,每下一個棋子後所算出的「無障礙四方形」數即為下該棋子的得分數。每位下棋者的總分即是該下棋者每個棋子的得分數總和。
請寫一個程式計算A 和 B 兩位下棋者的累計總分。
輸入說明

第一行輸入只有一個整數n,代表此盤棋共下了n (1 ≤ n ≤ 5,000)個棋子。接下來的n 行,每一行有兩個整數,依序代表這n 個棋子所放置的位置。
請注意,由於測試資料中確實包含n=5000 的輸入,你的程式必須非常的有效率才會通過所有的測試資料。

 

輸出說明

請輸出兩個整數,分別代表該盤棋兩位下棋者的累計得分數。先下棋者(A) 的分數在前,後下棋者(B)的分數在後,中間用一個空白隔開。

範例說明: 

範例輸入
4    <- 此盤棋共下了四步棋
2 3  <- 第一步棋A 下在 (2, 3) *這一步棋A 得0 分
3 4  <- 第二步棋B 下在 (3, 4) *這一步棋B 得1 分
1 2  <- 第三步棋A 下在 (1, 2) *這一步棋A 得2 分
4 1  <- 第四步棋B 下在 (4, 1) *這一步棋B 得5 分
7    <- 此盤棋共下了七步棋
1 5  <- 第一步棋A 下在 (1, 5) *這一步棋A 得0 分
2 7  <- 第二步棋B 下在 (2, 7) *這一步棋B 得1 分
3 8  <- 第三步棋A 下在 (3, 8) *這一步棋A 得2 分
5 1  <- 第四步棋B 下在 (5, 1) *這一步棋B 得5 分
6 2  <- 第五步棋A 下在 (6, 2) *這一步棋A 得9 分
7 3  <- 第六步棋B 下在 (7, 3) *這一步棋B 得13 分
4 4  <- 第七步棋A 下在 (4, 4) *這一步棋A 得10 分
範例輸出
2 6    <- 這盤棋累計得分為A 棋者2 分,B 棋者6 分
21 19  <- 這盤棋累計得分為A 棋者21 分,B 棋者19 分
測資資訊:
記憶體限制: 512 MB
公開 測資點#0 (100%): 10.0s , <1M
提示 :
標籤:
出處:
94學年度全國資訊學科能力競賽


編號 身分 題目 主題 人氣 發表日期
沒有發現任何「解題報告」