WC '18 Contest 3 S4 - Holey Travels

View as PDF

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

Author:
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, Pokémon trainers will be traveling over an open field which can be represented as an infinite 2D plane. The -th Pokémon trainer will be walking along the infinite, straight line which passes through two distinct points and . 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 -th trainer will have 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 , 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 of the points, .
In test cases worth another of the points, .

Input Specification

The first line of input consists of a single integer, , and one real number, .
lines follow, the -th of which consists of five space-separated integers, , , , , and , for .

Output Specification

Output a single integer, the maximum number of Pokémon which Team Rocket can trap. It's guaranteed that increasing or decreasing by up to 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

23

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

6

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 Pokémon) indicated in brown:

The second case is similarly illustrated below: