RGPC '17 P1 - Circle Clicking!

View as PDF
Submit solution
Points: 5
Time limit: 2.0s
Memory limit: 64M
Author:
chenj
Problem type

Kashif is a pretty big weeb Japanese animation enthusiast, so it's no surprise that he enjoys playing osu!, an anime-themed rhythm game. In this game, circles appear one-by-one on the screen, and players are required to move their cursor to them and click on them at just the right time to get points.

New circles usually appear close to the positions of previous circles, but they may occasionally appear on the other side of the screen as well (called "jumps"). Kashif can play well when the distance between two sequential circles is less than or equal to D, but if the distance is too great, he misses, and his combo (number of successful hits before the miss) resets to 0.

Given a sequence of coordinates of circles (points) in the form (x_i, y_i), Kashif wants to know what his greatest possible combo is, if he always hits the first point. For the purpose of this problem, assume that circles can only be hit at exactly the specified point.

Input Specification

The first line will contain 2 space-separated integers N (1 \le N \le 100\,000) and D (1 \le D \le 1\,000), representing the total number of circles in the sequence and Kashif's greatest jump distance respectively.

The next N lines will each contain 2 space-separated integers, x_i and y_i (-1\,000 \le x_i, y_i \le 1\,000), representing the coordinates of the i^{th} circle.

Output Specification

Output a single integer representing the longest possible combo Kashif can achieve.

Sample Input

5 5
0 0
1 1
2 1
2 -6
-1 -4

Sample Output

3

Comments


  • 0
    yellowsn0w1004  commented on Feb. 19, 2017, 8:46 p.m.

    After he misses, is his next click guaranteed or does it still have to be within his reach?


    • 0
      chenj  commented on Feb. 19, 2017, 11:22 p.m.

      Sorry for the late reply, but yes, his next click is guaranteed.


  • -2
    LOLWHATOMGBBQ  commented on Feb. 19, 2017, 5:01 p.m.

    Consider this test case.

    5 5
0 0
1 1
2 -7
2 -6
-1 -4

    Kashif can forgo the second circle to get a combo of 3, instead of getting a combo of 2 if he hits in order.


    • 2
      Kirito  commented on Feb. 19, 2017, 5:37 p.m.

      In osu! the circles must be clicked in the order they show up (I.E. no skipping).


  • 0
    gloomcore  commented on Feb. 18, 2017, 5:06 p.m. ← edited

    Can Kashif continue game after he misses for the first time? And should all circles be hit in consecutive way?


    • 0
      Kirito  commented on Feb. 18, 2017, 6:11 p.m.

      Yes, misses only affect combo, and yes, all circles must be hit in the order given in input.