TLE '17 Contest 7 P1 - Stargazing

View as PDF

Submit solution

Points: 3 (partial)
Time limit: 2.0s
Memory limit: 256M

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
Fax and Flaco stargazing with their bare eyes.

Fax McClad, Croneria's most observant bounty hunter, is out stargazing with his wingmate Flaco.

Using purely his keen eyesight, Fax collects data about the countless planets in the sky. The sky can be represented as a 2D Cartesian plane, where each planet can only occupy a single point. No two planets will be located at the same point.

To begin, Fax records an arbitrary first planet. He does not know the exact position of this planet. He then picks another planet and records its difference in position relative to a previously recorded planet, repeating this process until ultimately, all planets have been picked. Occassionally, Fax may accidentally pick a new planet that has already been previously picked.

Given Fax's data, can you help him determine the number of distinct planets in the sky? That is, how many distinct locations of planets will Fax have recorded?

Input Specification

The first line contains integer N (1 \le N \le 1\,000), the number of selected planets.
Note that this includes the first planet.

The following N - 1 lines each contain three integers P_i (1 \le P_i < i), X_i, and Y_i (-1\,000 \le X_i,Y_i \le 1\,000).
For the i^{th} line (2 \le i \le N), (X_i,Y_i) is the difference in X and Y coordinates of the i^{th} picked planet relative to the P_i^{th} picked planet.
Note that the difference between two values is calculated by the final value subtracting the initial value.

Output Specification

A single integer, the number of distinct planets in the sky.

Sample Input

1 7 8
2 3 2
1 10 10
4 -5 -5

Sample Output



Fax initially picks a first planet (that is not reflected in the input).
The second picked planet is located at (+7, +8) relative to the first planet.
The third picked planet is located at (+3, +2) relative to the second planet, which places it at (+10, +10) relative to the first planet.
However, the fourth picked planet is also located at (+10, +10) relative to the first planet. Since this coincides with the third picked planet, Fax can ignore this measurement.
The fifth picked planet is located at (-5, -5) relative to the fourth planet, thereby placing it at (+5, +5) relative to the first planet.
In total, there are 4 distinct planets.