1002 . 中樞灌溉系統
TopCoder
Tags
Description
在設計農業的灌溉設施時，除了傳統的溝渠以外，中樞灌溉系統是一種有效的替代方案，這個方法使用設置在中心的灑水器保持周圍的土壤溼潤，從上方看起來就像一個個的綠色的巨大圈圈，稱為作物圈。
水果王國在他們的土地上有 $n$ 塊這樣的作物圈，第 $i$ 個的圓心座落在 $(x_i, y_i)$ 的位置而半徑為 $r_i$。這些作物圈可能會相交或甚至互相包含。
傳奇芒果國王是水果王國的國王，為了改善王國的交通系統，他想要在土地上經過 $(s_x, s_y)$ 與 $(t_x, t_y)$ 的直線上興建一條條鐵路，雖然確切的鐵路線段還沒有被決定，國王害怕這條鐵路會傷害王國內傳統農業的發展，因此，國王想要知道有多少作物圈會落在這條直線上面。
由於你是這個國度裡最受人景仰的學者，傳奇芒果國王請求你幫忙完成這項重責大任。
Input Format
輸入的第一行有五個以空白分開的整數 $n, s_x, s_y, t_x, t_y$。
接下來的 $n$ 行中每行都有三個以空白分開的整數，第 $i$ 行的整數依序為 $x_i, y_i, r_i$，意義如題目所述。
- $1 \leq n \leq 10 ^ 5$
- $-10 ^ 4 \leq s_x, s_y, t_x, t_y, x_i, y_i \leq 10 ^ 4$
- $1 \leq r_i \leq 10 ^ 4$
- $(s_x, s_y) \neq (t_x, t_y)$
Output Format
輸出一個非負整數代表與直線相交的作物圈數量。如果有多個圓心與半徑皆相同的作物圈，相交的數量仍要重複計算。
Sample Input 1
3 0 0 3 4 3 -4 5 -4 -4 1 0 5 2
Sample Output 1
2
Sample Input 2
3 0 0 0 1 0 3 1 0 3 1 0 3 1
Sample Output 2
3
Hints
Problem Source
Subtasks
| No. | Testdata Range | Score |
|---|