b067. 6. 下棋問題 - 高中生程式解題系統

內容

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)的分數在後，中間用一個空白隔開。

範例說明：

範例輸入 #1

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 分

範例輸出 #1

2 6    <- 這盤棋累計得分為A 棋者2 分，B 棋者6 分
21 19  <- 這盤棋累計得分為A 棋者21 分，B 棋者19 分

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (100%): 10.0s , <1M

提示：

標籤:

出處:

94學年度全國資訊學科能力競賽

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