RGPC '17 P1 - Circle Clicking! - Olympiads Online Judge

RGPC '17 P1 - Circle Clicking!

Points: 5

Time limit: 2.0s

Memory limit: 64M

Author:

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$ $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)$ $(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$ $N$ $(1 \le N \le 100\,000)$ $(1 \leq N \leq 100 000)$ and $D$ $D$ $(1 \le D \le 1\,000)$ $(1 \leq D \leq 1 000)$ , representing the total number of circles in the sequence and Kashif's greatest jump distance respectively.

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

Output Specification

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

Sample Input

Copy

Sample Output

Copy

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.

Copy
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.