ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Timus Top Coders: First Challenge

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Fireflies

Time limit: 3.0 second
Memory limit: 64 MB


Beastly cold is chilling to the marrow. Blue radiance is scorching the eyes. The vortex of power is engulfing into the depth of the darkness which is impossible to return from… But it was not the end. Power and will prevail over all. By the last effort he raised his evanescent shadow and fell out from the darkness into the real world — straight onto cold floor.
Light wizard Anton Derevensky was lying in the middle of the room near a dilapidated sofa dolefully staring at the choppy ceiling. As a result of last night he had an insufferable headache as well as a strong desire to do something good. Something light.
Flies were flying within the room. A lot of flies. Dark creatures. They must be lead into the light. By several passes Mr. Derevensky froze all flies, so that they remained motionlessly fixed in the air. But last night’s feast required enormous energy costs, so Anton, who decided to inflame the flies to turn them to fireflies, was very surprised to discover that all his remained power is enough to create only one tiny fireball.


Mr. Derevensky had a drink of water and started to count the flies. It appeared that exactly N flies had been fixed in the air in expectation of their fate. Anton was running with a ruler all over the room all day long and finally calculated cartesian coordinates Xi, Yi and Zi of each fly. Light wizard has decided to lead into the light as more flies as possible using a single fireball which can be cast in any point of the room and launched in any direction. A trajectory of the fireball is a straight line. If a fly is hit by the fireball it turns to a firefly, and the fireball continues its flight in the same direction. Since Anton's lack of power you may neglect fireball's size and consider it as a point particle.


The first line contains the integer number N (1 ≤ N ≤ 2000). Each of the next N lines contains the integer numbers Xi, Yi and Zi (−107 ≤ Xi, Yi, Zi ≤ 107) for the corresponding fly.


You should output the maximal number of flies which can be turned to fireflies using the fireball.


-1 1 -1
0 1 2
0 0 -1
-2 -1 2
2 -1 -2
-1 0 2
Problem Author: Ilya Grebnov, Nikita Rybak, Dmitry Kovalioff
Problem Source: Timus Top Coders: First Challenge
To submit the solution for this problem go to the Problem set: 1422. Fireflies