2158 . 搶拉麵
TopCoder
Description
在競賽圈有個潛規則，你如果想要變強，你就要去吃碗拉麵，而且你吃的拉麵越好吃，你就會變得越強。
在天龍國裡，共有 $N, (N \leq 2 \times10^ 3)$ 家麵店，每一家拉麵店都能夠用三個參數表示 $x_i, y_i, d_i (-10^ 9 \leq x_i, y_i \leq 10^ 9), (1 \leq d_i \leq N)$
其中 $x_i, y_i$ 代表麵店的座標，而 $d_i$ 代表他們的拉麵美味程度，而且對於兩兩不同的麵店，他們的美味程度不會重複。
有 $M, (M \leq 2 \times 10^ 3)$ 位競賽選手散落在各地，第 $i$ 位選手現在在座標 $X_i, Y_i, (-10^ 9 \leq X_i, Y_i \leq 10^ 9)$，想要去吃拉麵。
每個人都想吃最好吃的拉麵，
可是如果每個人都擠在同一間拉麵店的話，就要等很久。
聰明的你想到了一個辦法。
你規定所有人都只能前往和它距離 $K$ 以內的拉麵店。
其中兩個座標 $(x_1, y_1), (x_2, y_2)$ 的距離定為 $max(|x_1-x_2|, |y_1-y_2|)$
在這樣的狀況下，所有人都會前往他可以去的拉麵店中，做出最美味拉麵的店。
這樣一來，就不會所有人都擠在同一間拉麵店裡了
現在，你想知道，在精確的限制下，最多能有幾間拉麵店有人光顧
Input Format
第一行 $2$ 個正整數 $N, M$ 分別代表拉麵店的數量及選手的數量
接下來 $N$ 行，每行都有三個整數 $x_i, y_i, d_i$ 其中意義參考題敘
接下來 $M$ 行，每行有兩個整數 $X_i, Y_i$ 其中意義參考題敘
Output Format
請輸出一個整數代表答案
Sample Input 1
1 1 1
2 1 2
2 3 3
0 1
1 3
3 3
Sample Output 1
Hints
關於範測一
當我們將 $K$ 設定為 1 的時候
編號為 1 的人將去 A (評價為 1) 的餐廳
而編號為 2, 3 都會去 C ( 評價為 3) 的餐廳
所以總共有兩間餐廳有人光顧
而且沒有其他的 $K$ 可以讓更多餐廳有人光顧
Problem Source
by kevin_zhang
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~4 | $N, M \leq 5$ | 8 |
| 2 | 5~9 | $N \leq 2$ | 8 |
| 3 | 10~14 | $(N, M \leq 50), (0 \leq x_i, y_i, X_i, Y_i \leq 100)$ | 20 |
| 4 | 15~19 | $0 \leq x_i, y_i, X_i, Y_i, \leq 1000$ | 24 |
| 5 | 0~34 | No additional limits | 40 |