Description

Canmuu is out for revenge after being utterly defeated by Bessie in paintball and has challenged Bessie to a video game.

In this game, Bessie starts at point $(BX, BY)$ in the coordinate grid ($-1{,}000 \le BX \le 1{,}000$; $-1{,}000 \le BY \le 1{,}000$) at time $0$. She moves continuously with velocity $(BVX, BVY)$ units per second ($-100 \le BVX \le 100$; $-100 \le BVY \le 100$). Thus, at time $1$ she will be at point $(BX + BVX, BY + BVY)$; at time $1.5$ she will be at $(BX + 1.5 \times BVX, BY + 1.5 \times BVY)$.

Unfortunately, Canmuu has sent $N$ ($1 \le N \le 50{,}000$) cattle bruisers to pursue Bessie. At time $t = 0$, cattle bruiser $i$ is at position $(X_i, Y_i)$ ($-1{,}000 \le X_i \le 1{,}000$; $-1{,}000 \le Y_i \le 1{,}000$) with velocity $(VX_i, VY_i)$ units per second ($-1{,}000 \le VX_i \le 1{,}000$; $-1{,}000 \le VY_i \le 1{,}000$).

Each cattle bruiser carries a "proximity" weapon that can hurt Bessie when the cattle bruiser is no farther than $R$ ($1 \le R \le 2{,}500$) units from her.

Bessie has a shield to protect herself from these attacks. However, she does not want to waste any of her shield’s power, so she would like to know the maximum number of cattle bruisers within firing range at any (possibly non-integer) time.

To avoid precision errors with real numbers, it is guaranteed that the answer remains the same whether the attack range is decreased to $R - 10^{-4}$ or increased to $R + 10^{-4}$.

Input Format

• Line $1$: Six space-separated integers: $N$, $R$, $BX$, $BY$, $BVX$, $BVY$.
• Lines $2$ to $N + 1$: Line $i + 1$ contains four space-separated integers: $X_i$, $Y_i$, $VX_i$, $VY_i$.

Output Format

• Line $1$: Print a single integer denoting the maximum number of cattle bruisers within attack range at any point in time.

3 1 0 0 0 2 
0 -3 0 4 
1 2 -1 1 
1 -2 2 -1 

2 

Hint

Bessie starts at point $(0, 0)$ and is moving at $2$ units per second in the positive y-direction. There are $3$ cattle bruisers; the first starts at point $(0, -3)$ and travels $4$ units per second in the y-direction. The maximum distance for a cattle bruiser to be in range of Bessie is $1$ unit.

At time $1.5$, Bessie is at point $(0, 3)$, and the three bruisers are at points $(0, 3)$, $(-0.5, 3.5)$, and $(4, -3.5)$. The first two cattle bruisers are within $1$ unit of Bessie, while the third will never be within $1$ unit of Bessie, so the maximum achievable number is $2$.

Translated by ChatGPT 5