P5927 [JSOI2010] Chess Placement Problem

There is a new puzzle game.

This game is played by two players, A and B, who take turns placing pieces on the grid intersection points of a $1000000\times1000000$ square chessboard. The coordinates of a grid intersection point are written as $(x,y)$, where $(0, 0)$ represents the point at the bottom-left corner of the board. No two pieces may be placed on the same coordinate. Each time a new piece is added, the counter on the board automatically computes the number of `unblocked squares` that can be formed by the pieces currently on the board. An `unblocked square` means a square defined by any two pieces such that the interior of the square contains no other pieces. After each move, the number of `unblocked squares` computed is the score obtained for placing that piece. Each player's total score is the sum of the scores for all pieces they have placed. Write a program to compute the cumulative total scores of players A and B.

The first line contains a single integer $n$, indicating that a total of $n$ pieces are placed in this game. The next $n$ lines each contain two integers, in order, representing the positions where these $n$ pieces are placed.

Output two integers, representing the cumulative scores of the two players in this game. A's score comes first, and B's score comes second, separated by a single space.

For $100\%$ of the testdata, $1\le n\le5000$, $0\le x,y\le 1,000,000$. Translated by ChatGPT 5