1151 . 6.下棋問題
TopCoder
Description
問題敘述：
eToy 發明了一個新的益智遊戲，該遊戲由A 和B 兩人輪流在一個1,000,000x 1,000,000 的方格棋盤上的格線交點下棋，格線交點的座標以（x, y）, 0 ≤ x , y ≤1,000,000 表示之，(0, 0)代表棋盤最左下角那點。
每一個棋子放置的位置不可以與任何其它棋子在同一X 座標或Y 座標上，棋盤上新增加一個棋子時，棋盤上的計數器會自動算出以目前棋盤上棋子所能夠圍成的「無障礙四方形」數。
「無障礙四方形」是指以任意兩個棋子所定義出的四方形內部不含其它棋子，每下一個棋子後所算出的「無障礙四方形」數即為下該棋子的得分數。每位下棋者的總分即是該下棋者每個棋子的得分數總和。
請寫一個程式計算A 和 B 兩位下棋者的累計總分。
Input Format
第一行輸入只有一個整數n，代表此盤棋共下了n (1 ≤ n ≤ 5,000)個棋子。接下來的n 行，每一行有兩個整數，依序代表這n 個棋子所放置的位置。
請注意，由於測試資料中確實包含n=5000 的輸入，你的程式必須非常的有效率才會通過所有的測試資料。
Output Format
請輸出兩個整數，分別代表該盤棋兩位下棋者的累計得分數。先下棋者(A)的分數在前，後下棋者(B)的分數在後，中間用一個空白隔開。
Sample Input 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 分
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 分
Sample Output 1
2 6 <- 這盤棋累計得分為A 棋者2 分，B 棋者6 分
Sample Input 2
//（不包含<-以及後面的字）
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 分
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 分
Sample Output 2
21 19 <- 這盤棋累計得分為A 棋者21 分，B 棋者19 分
Hints
Problem Source
原TIOJ1151 / 94全國賽(prob 6)。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 20 |
| 2 | 1 | 20 |
| 3 | 2 | 20 |
| 4 | 3 | 20 |
| 5 | 4 | 20 |