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
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 assignments 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.


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

0.00 0.00 1.00
3.00 0.00 1.00
3.00 3.00 1.00

Sample Output



There are no comments at the moment.