b446.
史蒂芙的煩惱
內容
背景
動畫 遊戲人生《No Game No Life》中，史蒂芙 (Stephanie Dola) 常常被欺負，儘管她以學院第一畢業，對於遊戲一竅不通的她在這個世界常常被欺負。現在就交給你來幫幫她。
問題描述
兩個人輪流在一個大棋盤上下棋，每一步棋的得分根據這一步棋與最鄰近的敵方棋子的曼哈頓距離。
對於兩個點 $p, q$ 座標 $(p_x, p_y), (q_x, q_y)$，曼哈頓距離 (Manhattan distance) 為 $|p_x - q_x| + |p_y - q_y|$。
輸入說明
每組測資只有一筆，第一行一個整數 $N$，表示兩方輪流下 $N$ 步棋。接下來會有 $2N$ 行，奇數行為玩家史蒂芙下棋的座標，偶數行為玩家空下棋的座標。
- $1 \le N \le 50000$
- 棋座標 $(x, y)$，範圍 $0 \le x, y \le 32767$
- 保證每一個座標最多只會有其中一方的棋子
輸出說明
除了先手的第一步，每一步都找到最鄰近敵方旗子的曼哈頓距離。
範例輸入
#1
3 1 1 5 5 4 4 3 2 2 4 2 3
範例輸出
#1
8 2 3 3 1
測資資訊：
記憶體限制：
512
MB
提示 ：
- 測資中，稠密、稀疏情況都有可能。
- 範例輸入如下圖所示 史蒂芙 (A)、空 (B)
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
|A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | | |A1| | | | |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | | | | | | | | | | | | | | | | | | |A3| | | | |B3|A3| |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | +-> | | | | | | +-> | | | | | | +-> | |B2| | | | +-> | |B2| | | | +-> | |B2| | | |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | | | | | | |A2| | | | | |A2| | | | | |A2| | | | | |A2| |
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
| | | | | | | | | | |B1| | | | | |B1| | | | | |B1| | | | | |B1| | | | | |B1|
+--------------+ +--------------+ +--------------+ +--------------+ +--------------+ +--------------+
出處:
[管理者：
morris1028
(碼畜)
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||