背景
動畫 遊戲人生《No Game No Life》中,史蒂芙 (Stephanie Dola) 常常被欺負,儘管她以學院第一畢業,對於遊戲一竅不通的她在這個世界常常被欺負。現在就交給你來幫幫她。
問題描述
兩個人輪流在一個大棋盤上下棋,每一步棋的得分根據這一步棋與最鄰近的敵方棋子的曼哈頓距離。
對於兩個點 $p, q$ 座標 $(p_x, p_y), (q_x, q_y)$,曼哈頓距離 (Manhattan distance) 為 $\vert p_x - q_x\vert + \vert p_y - q_y\vert $。
輸入格式
每組測資只有一筆,第一行一個整數 $N$,表示兩方輪流下 $N$ 步棋。接下來會有 $2N$ 行,奇數行為玩家史蒂芙下棋的座標,偶數行為玩家空下棋的座標。
- $1 \le N \le 50000$
- 棋座標 $(x, y)$,範圍 $0 \le x, y \le 32767$
- 保證每一個座標最多只會有其中一方的棋子
輸出格式
除了先手的第一步,每一步都找到最鄰近敵方旗子的曼哈頓距離。
範例輸入
3
1 1
5 5
4 4
3 2
2 4
2 3
範例輸出
8
2
3
3
1
解說
範例輸入如下圖所示 史蒂芙 (A)、空 (B)
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
|A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | | | | | | | | | | | | | | | | | | |A3| | | | |B3|A3| |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | +-> | | | | | | +-> | | | | | | +-> | |B2| | | | +-> | |B2| | | | +-> | |B2| | | |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | | | | | | |A2| | | | | |A2| | | | | |A2| | | | | |A2| |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | |B1| | | | | |B1| | | | | |B1| | | | | |B1| | | | | |B1|
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+