Mock CCC '19 Contest 2 S4 - Tudor Walks Among the Goats

Points: 25 (partial)

Time limit: 3.0s

Memory limit: 1G

Problem type

Tudor is going for a walk!

In this scenario, Tudor has $N$ $N$ goats tied to fence posts at various locations with varying lengths of ropes. Tudor is going to go walking on an infinite line. If, at any point along the walk, a goat is able to reach Tudor, even at the maximal range of the rope, then the goat will run at Tudor. Tudor will then be able to check on the goat to make sure that it's in fine health.

The goats are rather territorial, so Tudor's initial assignment of rope lengths to goats ensures that two goats can never interact with each other, not even at a single point.

Compute the maximum number of goats that Tudor can check on given that he can choose what line to travel on.

Constraints

$1 \le N \le 2000$ $1 \leq N \leq 2000$

In tests worth 5 marks, $N \le 500$ $N \leq 500$ .

$-10^6 \le x_i, y_i \le 10^6$ $- 10^{6} \leq x_{i}, y_{i} \leq 10^{6}$

$1 \le l_i \le 100$ $1 \leq l_{i} \leq 100$

Input Specification

The first line of input will contain a single positive integer, $N$ $N$ .

Each of the next $N$ $N$ lines will contain three space-separated floating point numbers specified to exactly two decimal places, $x_i$ $x_{i}$ , $y_i$ $y_{i}$ , and $l_i$ $l_{i}$ , indicating that goat $i$ $i$ is tied to a fence post at $(x_i, y_i)$ $(x_{i}, y_{i})$ with a rope of length $l_i$ $l_{i}$ .

Output Specification

Output, on a single line, the maximum number of goats Tudor can visit.

Sample Input

Copy

3
0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00

Sample Output

Copy

Comments

-2

MarksonChen commented on May 30, 2021, 5:57 p.m.

Question unclear. Is the "line" Tudor travelling on always a horizontal/vertical line? Or can it be any straight lines on a grid?

2

chika commented on May 31, 2021, 7:59 a.m.

Question unclear.

What is unclear about the question?

Is the "line" Tudor travelling on always a horizontal/vertical line? Or can it be any straight lines on a grid?

Does the problem statement give any constraints on the form of the infinite line?