2016年2月4日 星期四

[IOI Camp Judge 37]動態曼哈頓最短距離 (題目備份)

IOI Camp Judge是暫時性的,因此在此做題目備份
題解在這裡

動態曼哈頓最短距離

Time Limit: 8s

Description

定義二維平面上兩個點 (x1,y1),(x2,y2) 的曼哈頓距離為 |x1x2|+|y1y2|
你現在要維護一個集合 S(一開始為空集合),並且將進行一連串操作,操作有兩種:
  • 將二維平面上一個整數點(座標皆為整數)(x,y) 放到 S 裏面
  • 問 S 裏面與 (x,y) 曼哈頓距離最近點的距離為多少

Input Format

第一行有一個正整數 T,代表總共有幾筆測試資料。每筆測試資料第一行包含一個正整數 N,代表操作數。接下來包含 N 行,每行包含三個正整數 t,x,y。若 t 爲 0 代表插入操作,請將 (x,y) 放進 S 裡。若 t 爲 1 代表詢問操作,請輸出 S 裡離 (x,y) 的曼哈頓距離最小是多少。
  • 1T5
  • 1N2×105
  • 1x,y106
  • 保證第一個操作是插入操作

Output Format

對於每個詢問操作,請輸出一行包含一個整數,代表詢問的答案。

Sample Input

1
10
0 1 3
0 2 4
1 3 4
1 2 120
0 1 4
0 1 3
1 1 2
1 1 1
0 1 4
1 2 4

Sample Output

1
116
1
2
0

沒有留言:

張貼留言

歡迎留言或問問題~
若您的留言中包含程式碼,請參考這篇
如果留言不見了請別慌,那是因為被google誤判成垃圾留言,小莫會盡快將其手動還原