Probably, you visited airports in which airplanes take off every minute or even more frequently. And did you ever imagine how many airplanes there are in the air simultaneously? And what about the whole globe?
Assume that the Earth is an ideal ball with center at (0, 0, 0) and radius 6370 kilometers.
Most passenger planes fly at a height not more than 15
kilometers. If you could look at the Earth from the outside,
the planes would look as points on its surface. Suppose that at
some moment there are N planes in the air. A plane number
i is at the point of intersection of the Earth sphere
with the ray starting at the origin and having directing vector
(Xi, Yi, Zi).
There is not more than one plane at each point of the Earth's
surface. You task is to determine the maximal number of planes
that can be seen simultaneously from a very large distance from
the Earth. From this distance, an open hemisphere of the Earth's surface can be observed.
The first line contains an integer N (1 ≤ N ≤ 150).
The next N lines contain triples of integers Xi,
Yi, Zi, which are directing vectors
of the rays passing through the planes. The absolute values of
these numbers do not exceed 600, and each triple contains at least one nonzero number.
You should output the maximal number of planes that can be seen simultaneously from a very large distance from the Earth.
0 0 1
0 0 -1
0 1 0
0 -1 0
1 0 0
-1 0 0
Problem Author: Dmitry Ivankov
Problem Source: Ural SU and Orel STU Contest. Petrozavodsk Summer Session, August 2006