Woburn Challenge 2018-19 Round 3 - Senior Division

Problem 4: Holey Travels

When it comes down to it, there's nothing that the members of Team Rocket enjoy more than the simple, familiar things in life. In other words, digging holes to trap Pokémon trainers and steal their Pokémon.

Today, N (1 ≤ N ≤ 1000) Pokémon trainers will be traveling over an open field which can be represented as an infinite 2D plane. The i-th Pokémon trainer will be walking along the infinite, straight line which passes through two distinct points (X1i, Y1i) and (X2i, Y2i) (−10,000 ≤ X1i, Y1i, X2i, Y2i ≤ 10,000, (X1i, Y1i) ≠ (X2i, Y2i)). Multiple trainers may walk along exactly the same path. Note that each path extends infinitely in both directions (it's neither a line segment nor a ray). Team Rocket don't care in which direction along this path the trainer will be walking. What they do care about is the fact that the i-th trainer will have Pi (1 ≤ Pi ≤ 1,000,000) Pokémon with them!

Jessie, James, and Meowth have time to dig a single hole somewhere on this infinite field before the trainers begin walking along their paths. This hole will be a circle with real-valued radius R (1 ≤ R ≤ 100,000), centered at any point (with real-valued coordinates) of their choice.

Once the hole has been dug, each trainer whose path turns out to intersect with or touch the hole's circle (inclusively) will fall into it, with all of their Pokémon becoming trapped in the hands of Team Rocket. What's the maximum number of Pokémon which Team Rocket can trap by choosing an optimal excavation location?


In test cases worth 8/40 of the points, N ≤ 2.
In test cases worth another 20/40 of the points, N ≤ 100.

Input Format

The first line of input consists of a single integer, N, and 1 real number, R.
N lines follow, the i-th of which consists of five space-separated integers, X1i, Y1i, X2i, Y2i, and Pi, for i = 1..N.

Output Format

Output a single integer, the maximum number of Pokémon which Team Rocket can trap. It's guaranteed that increasing or decreasing R by up to 10−5 would not change the answer.

Sample Input 1

4 3.0
3 0 5 4 3
-2 5 7 0 8
-5 -5 7 1 9
1 6 -7 1 12

Sample Output 1


Sample Input 2

5 2.1
2 1 6 1 2
3 -2 -5 -2 3
7 5 1 5 2
-5 -3 -4 -3 1
-6 -7 4 -7 4

Sample Output 2


Sample Explanation

The following diagram illustrates the first case, with the Pokémon trainers' paths indicated in blue, and one possible optimal hole location (trapping 3 + 8 + 12 = 23 Pokémon) indicated in brown:

The second case is similarly illustrated below:

All Submissions
Best Solutions

Point Value: 20 (partial)
Time Limit: 5.00s
Memory Limit: 16M
Added: Feb 01, 2019
Author: SourSpinach

Languages Allowed:

Comments (Search)

It's quiet in here...