Hide

Problem E
Mountainpeeker

/problems/mountainpeeker/file/statement/en/img-0001.png
Illustration of sample 4. Joel can see all mountain peaks except the left-most and the right-most ones. Please note that the positions of the valleys are arbitrary, and you only need to consider the positions of the peaks to solve the problem.

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 (1n105), the number of other mountains to consider.

The second contains the integer h, the height of the mountain Joel is at. (0h8848)

The following n each contain the integers x and y (105x105, 0y8848), 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

N1000,x>0

3

10

N1000

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
Hide

Please log in to submit a solution to this problem

Log in