290. Defend the Milky Way
time limit per test: 0.25
memory limit per test: 65536
Year 22204. An alien invasion threatens the Milky Way. It seems like our entire civilization can be demolished. To prevent this, mankind has to build an immensely strong defense system using a brand new weapon invented in the 223rd Century: great laser net. Such net looks like a big laser triangle destroying everything it touches. To set up such laser triangle, you need laser control towers in its vertices. Of course, laser control towers can only be built at star systems, and at most one laser control tower is allowed at one star system.
But this weapon is the most expensive thing in the history of mankind, its cost being proportional to the area of the laser triangle. Laser control towers are way cheaper.
Qc, the greatest mathematician of the time and the commander of human armies, wants to build several laser nets in such a way that no alien can reach a Milky Way star system without being killed by laser. And, of course, he would like the system to be as cheap as possible. So he would like laser triangles to surround the convex hull of all the stars of the Milky Way star system.
If a star is inside or on the border of a laser triangle, you also have to build a laser control tower there to prevent it from being destroyed by laser.
The first line of input contains one integer n (1 <= n <= 100) --- the number of star systems. Next n lines contain descriptions of the star systems: star name (containing characters with ASCII codes from 32 to 255) and its Cartesian coordinates in space (x, y and z). Length of star name doesn't exceed 200, all coordinates are integers not exceeding 10000 by absolute value. Star name and x-coordinate and consecutive coordinates will be separated with a single space.
On the first line of output print the number q of laser control towers to be built. In next q lines output the names of star systems for these towers, ordered alphabetically.
Qc 0 0 0
He 10000 10000 10000
Altair 2 0 0
Jupiter 0 2 0
Orion 0 0 2
Wx 1 1 0
Statz 0 -5 -5
Unreal -5 0 0
Qc -1 -1 0
|Author:||Anton Golubev, Petrazavodsk SU
|Resource:||Anton Golubev (Hedgehog)'s Contest #2 from Annual Summer Russian Teams Meeting in Petrozavodsk State University
|Date:||August 26, 2005
|Server time: 2017-09-23 04:09:56||Online Contester Team © 2002 - 2016. All rights reserved.|