| 2025 ICPC, Chula Selection Contest |
|---|
| Finished |
There are $$$n$$$ vertical poles standing on a straight line at integer positions $$$x = 1,2,\dots,n$$$. The $$$i$$$-th pole has height $$$h_i$$$ and is located at $$$x = i$$$.
Sunlight comes from the left and travels in the direction of the vector $$$\vec{d} = (t_x, t_y)$$$ with $$$t_x \gt 0$$$. This means the rays propagate toward increasing $$$x$$$, with vertical slope determined by $$$t_y/t_x$$$.
A pole is ray cast (its top is directly lit) if its top lies strictly above the shadow envelope formed by all poles to its left.
Your task is to count how many poles are ray cast.
The first line contains $$$t$$$ ($$$1 \le t \le 150\,000$$$) — the number of test cases.
The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 5 \cdot 10^{5}$$$) — the number of poles.
The second line contains $$$n$$$ integers $$$h_1, h_2, \ldots, h_n$$$ ($$$1 \le h_i \le 10^{9}$$$) — the heights of the poles.
The third line contains two integers $$$t_x$$$ and $$$t_y$$$ ($$$1 \le t_x \le 10^{9}$$$, $$$-10^{9} \le t_y \le 10^{9}$$$) — the components of the sunlight direction vector $$$\vec{d}$$$.
It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^{5}$$$.
For each test case, print a single integer — the number of poles that are ray cast.
452 3 2 7 42 155 7 4 6 32 -145 5 5 53 033 10 71 -2
3 2 1 2
Figure 1 corresponds to the first test case with $$$h = [2,3,2,7,4], t_x = 2, t_y = 1$$$.
Figure 2 corresponds to the second test case with $$$h = [5,7,4,6,3], t_x = 2, t_y = -1$$$.
| Name |
|---|


