10017. Fast Dynamic Nearest Neighbors Search

I'm a slow walker, but I never walk backwards.

背景

動畫 遊戲人生《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|  
+--------------+     +--------------+     +--------------+     +--------------+     +--------------+     +--------------+

Discussion