WC '18 Contest 3 S4 - Holey Travels

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.5s
Memory limit: 16M

Problem type
Woburn Challenge 2018-19 Round 3 - Senior Division

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 \le N \le 1\,000) 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 (X1_i, Y1_i) and (X2_i, Y2_i) (-10\,000 \le X1_i, Y1_i, X2_i, Y2_i \le 10\,000, (X1_i, Y1_i) \ne (X2_i, Y2_i)). 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 P_i (1 \le P_i \le 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 \le R \le 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 \le 2.
In test cases worth another 20/40 of the points, N \le 100.

Input Specification

The first line of input consists of a single integer, N, and one real number, R.
N lines follow, the i-th of which consists of five space-separated integers, X1_i, Y1_i, X2_i, Y2_i, and P_i, for i = 1 \dots N.

Output Specification

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:


There are no comments at the moment.