LCC '22 Contest 2 S3 - Round Nuts

View as PDF

Submit solution


Points: 7 (partial)
Time limit: 2.0s
Java 2.5s
Python 2 2.5s
Python 3 2.5s
Memory limit: 64M
Java 128M
PyPy 2 128M
PyPy 3 128M

Author:
Problem type

Nibbles the Squirrel is participating in a hackathon and has decided to create a Virtual Roundtable as her project. The roundtable will be shaped like a nut, and Nibbles wants to minimize the bluntness of the table for it to be as round as possible.

Her computer screen has N pixels, with pixel i located at integer coordinates (x_i, y_i) and has a distance of d_i from the origin (0, 0) (i.e. d_i can be calculated as \sqrt{x_i^2+y_i^2}), let's define the bluntness of a roundtable as the absolute difference between the maximum and minimum d_i of any pixel on the roundtable (i.e. max(d_i) - min(d_i)). Nibbles wants to choose a subset of her N pixels to be part of her rountable such that the bluntness of the rountable does not exceed B.

What is the maximum number of pixels that can be part of her roundtable while satisfying this constraint?

Constraints

In all test cases, 1 \le N \le 2 \times 10^5, 1 \le B \le \sqrt{8} \times 10^8, -10^8 \le x_i, y_i \le 10^8.

Subtask 1 [20%]

N \le 18

Subtask 2 [30%]

N \leq 2 \times 10^3

Subtask 3 [50%]

No further constraints.

Input Specification

First line: N (the number of pixels on Nibbles's computer screen), and B (the maximum bluntness of the roundtable).

Next N lines: (x_i, y_i), the coordinates of pixel i.

Output Specification

One integer: the maximum number of pixels that can be part of Nibbles's roundtable.

Sample Input 1

9 1
1 0
0 1
-1 0
0 -1
1 1
-3 0
1 4
4 1
1 -3

Output for Sample Case 1

5
Explanation for Sample Case 1

Explanation Diagram for Sample Case 1

For the outlined roundtable, the farthest point from the origin (E) has a distance of \sqrt{2}, and the closest distance of any point to the origin is 1.

Therefore, the bluntness of the roundtable above is \sqrt{2} - 1 which does not exceed 1.


Comments

There are no comments at the moment.