The Cosmic Era P4 - Freedom Appears!

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Problem type

The Archangel is under attack and about to be destroyed! Luckily, Kira arrives in his ZGMF-X10A Freedom Gundam! He needs you to help him with the targeting of his beams! Kira and his Freedom Gundam is located at (X_k, Y_k, Z_k) (-10^{17} \le X_k, Y_k, Z_k \le 10^{17}). There are N (1 \le N \le 10^5) enemy Mobile Suits numbered from (1, 2, \dots, I-1, I) that he needs to destroy. Each enemy is located at a position (X_i, Y_i, Z_i) (-10^{17} \le X_i, Y_i, Z_i \le 10^{17}). We assume that the enemy Gundams are points, and none of the Gundams (including Kira) are located at the same position. The Freedom Gundam can only fire lasers along a straight path. But, as an upside, when Kira fires his laser beam, it will instantly destroy everything in its path.

Kira wants you to tell him the minimum number of times that he needs to fire his laser beam.

Input Specification

The first line will have 3 integers, (X_k, Y_k, Z_k), each separated by a space. The second line will have the integer N. The next N lines will each have 3 integers, the coordinates of an enemy mobile suit (X_i, Y_i, Z_i), each separated by a space.

Sample Input

0 0 0
1 1 0
2 2 0
-1 2 3

Output for Sample Input


Explanation of Output for Sample Input

(0,0,0), (1,1,0), and (2,2,0) all lie on the same line, so he can destroy 2 enemies with 1 shot. And he needs 1 more shot to destroy the mobile suit that lies on (-1,2,3).


  • 10
    Kirito  commented on May 17, 2016, 10:21 p.m.

    Does the Gundam only shoot in 1 direction at a time?

    I.E. if there is one enemy in front of the Gundam and one right behind such that the Gundam and two enemies are collinear, it still takes 2 shots, right?