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

View as PDF
Submit solution
Points: 25 (partial)
Time limit: 3.0s
Memory limit: 1G
Problem type

Tudor is going for a walk!

In this scenario, Tudor has 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

In tests worth 5 marks, N \le 500.

-10^6 \le x_i, y_i \le 10^6

1 \le l_i \le 100

Input Specification

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

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

Output Specification

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

Sample Input

3
0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00

Sample Output

2

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?