<PREV Problem:
NEXT>
Solved by 92 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

Star War (epizode V)

Time limit = 5 seconds

A long time ago in the galaxy far, far away.

After the Death Star had been destroyed by rebels, a group of imperial scientists started the development of new project "Death Star 2". New Star was provided by Death Ray, which destroys any object on its way and continue its passage in the original direction. For this time the resistance movement was expanded on many planets. The Emperor naturally disliked it. He gave the order to Dark Lord and Greatest Jedi Dart Vader to destroy the maximum number of planets with rebellious bases. Unfortunately, a very much time is required for recharging Death Ray, therefore Empire has one attempt only.

Help Lord Vader to choose position of new Death Star and the launch direction of the Death Ray such that the maximum number of planets is destroyed by one strike. And let the Evil Side of the Power will be with you!

Input The first line contains the number of rebellious planets N (2 ≤ N ≤ 200). Then N lines follow. Each line contains coordinates of planet x, y (integers in the range -32768 .. 32767) and its radius R (integer in the range 1..32767). The numbers is separated by one space.

Output Write in the output file the maximum number of planets, which can be destroyed by one strike of new Death Star.

Input#1
3
0 0 1
6 -1 1
3 1 2
Output#1
3
Input#2
4
5 0 1
0 5 1
-5 0 1
0 -5 1
Output#2
2

Author:
Semi-final of Ukraine student programming contest, March 2003, Khmelnitski.

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 190ms

SW soft NIX
ID = 54.161.108.158