Problem E
Mountainpeeker

Joel has spent a lot more time climbing mountains than programming the last 6 months, and he once again finds himself on top of another mountain. This time he has climbed a very special mountain range, where all the mountain tops are on a single line. The mountain Joel has climbed is $h$ meters high, and he is at relative horizontal position $0$ in the mountain range. Given the coordinates of $n$ other mountains in the range, you need to calculate how many of them Joel can actually see. You should assume that Joel is laying on the ground when looking for other mountains, hugging the mountain he has climbed (he does after all like the mountains very much).
Joel can see a mountain peak at $(x^*, y^*)$ if and only if there are no other mountain peaks placed above or on the line segment formed between his position $(0, h)$ and $(x^*, y^*)$
Input
The first line contains the integer $n$ $(1 \leq n \leq 10^{5})$, the number of other mountains to consider.
The second contains the integer $h$, the height of the mountain Joel is at. $(0 \leq h \leq 8848)$
The following $n$ each contain the integers $x$ and $y$ ($-10^{5} \leq x \leq 10^{5}$, $0 \leq y \leq 8848$), the coordinates of another mountain top. $x$ describes the horizontal relative position to Joel, and $y$ is the height of the mountain. It is also guaranteed that no two peaks have the same $x$ value.
Note that $x$ may be negative!
Output
Print an integer: the number of other mountain tops Joel can see.
Scoring
Your solution will be tested on a set of test groups, each worth a number of points. Each test group contains a set of test cases. To get the points for a test group you need to solve all test cases in the test group.
Group |
Points |
Constraints |
$1$ |
$10$ |
$N = 2,\; x > 0$ |
$2$ |
$30$ |
$N \leq 1000,\; x > 0$ |
$3$ |
$10$ |
$N \leq 1000$ |
$4$ |
$50$ |
No additional constraints. |
Explanation of Sample 1
The first peak at $(1, 7)$ lies perfectly on the line segment between Joel $(0, 7)$ and the second peak $(2, 7)$. By our defintion of being able to see a mountain peak, this means Joel can NOT see the second peak.
Sample Input 1 | Sample Output 1 |
---|---|
2 7 1 7 2 7 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
3 0 3 4 1 1 4 3 |
2 |
Sample Input 3 | Sample Output 3 |
---|---|
2 0 1 1 -1 1 |
2 |
Sample Input 4 | Sample Output 4 |
---|---|
5 3 1 3 2 3 -1 3 -2 4 -3 2 |
3 |