TLE '17 Contest 4 P4 - Willson and Target Practice

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 8.0s
Java 12.0s
Python 16.0s
Memory limit: 512M

Authors:
Problem types
The poor unsuspecting targets don't see it coming...

Willson the Canada Goose is like any other Canada Goose - he likes to engage in target practice.

There are N unsuspecting targets that Willson can practice on. The i^{th} target is located at (x_i,y_i).

Unlike other geese who choose a circular area for target practice, Willson is unique and decides to choose an equilateral triangle with side length K as his area, with the additional constraint that one side of the triangle must be parallel to the line y = 0.

Could you tell Willson the maximum number of targets that could be in such an area?

Note: A target on the perimeter of the triangle is counted.

Constraints

For all subtasks:

1 \le N \le 20\,000

1 \le K \le 200

All coordinates c satisfy \left|c\right| \le 2\,000.

SubtaskPointsAdditional Constraints
15K=1
215N=2
320N \le 200
430N \le 2\,000
530No additional constraints

Note 1: There can be multiple targets at the same coordinate.

Note 2: Python users are recommended to submit in PyPy.

Input Specification

The first line of input will contain two integers, N and K.

N lines of input follow. The i^{th} line will contain two integers, x_i and y_i.

Output Specification

Output a single integer, the maximum number of targets that can be in an area as described above.

Sample Input

5 3
1 1
2 0
2 4
3 2
3 3

Sample Output

3

Diagram


Comments


  • 0
    kedrist  commented on Dec. 24, 2017, 12:43 p.m. edit 2

    Hey, I'm getting TLE'd on case 27. My complexity is O(NK). When I'm stress testing it on my machine, it's working fine. Any special case that I might be missing ?

    Update - Thanks, I got it.