0142. Saturn

Input file name:	saturn.in
Output file name:	saturn.out
Time limit:	2 s
Memory limit:	64 megabytes

The problem (or isn't it a problem for you?):
10'000'000 years ago a great explosion took place and the Petrozavodsk macaroni factory forcing a great field of small asteroids to leave the Earth mother; guess what these asteroids were... These asteroids headed towards the planet Saturn which was a simple planet those days, i.e. it had no rings. After a great impact asteroids formed several rings under different angles causing numerous blackouts to happen on Earth and an Ice age came through the constant darkness. Anyway, the factory leaders survived the chaos and wished to eliminate the effects of the cataclysm they spawned. It was decided to send an experienced kamikaze terrorist Malchish Kibalchish towards the planet Saturn to bomb the planet using him and his nuclear belt (the job he does only for money). However the results were even worse. The rings left planet Saturn and spread across the Solar system. This caused the longest blackout in the Earth history, many dinosaurs died that year. Now it comes up to you. You are a new brave person wishing to remove these damn rings or eat them, whichever comes first... After making some research you have found that the factory used numerous highly flammable chemicals to make their macaroni so colorful and thus profitable. Burning one ring will cause such a big flare that all other rings forming a chain with it will also burn down. After you blow those rings, a great spark will happen and ice will melt. But this is right what you want because some idiot will describe it as "The Great Flood" and you will be known as the one who saved a lot of species. Now it's up to you to inscribe self into the history. To do this you need to find the minimal number of shots required to burn down all the rings, provided each shot is targeted to not yet burnt ring and that you never miss a target. Now let's define what ring, chain, etc┘ are:

Ring - a circle in 3D space.

Two rings A and B are said to be "connected" if ring A cannot be continuously moved away from ring B to any arbitrary distance without crossing ring B. Moving away implies arbitrary movement, rotation, etc┘ any continuous motion which does not affect the shape of A.

Chain - a set of rings, such that for any two rings A and B in the chain there is a path from A to B via connected ring pairs. A set with zero or only one ring is also considered to be a chain. Unlike "normal" chains, these can fork and have loops. The only requirement for ring set to be a chain is that it must be "connected" as described above.

Given all the rings, you are to find the minimal number of shots required to blow them all. Again, blowing one rings blows all the chain it belongs to.

Input file

The first line has the number k (1 ≤ k ≤ 1000) which stands for number of rings. k lines follow, each describes a ring as three triples of x y z coordinates. The first triple stands for the circle center. Two other triples stand for any two points on the ring itself. These points are not opposite and not the same, i.e. the ring is strictly defined by its center and two other points. All coordinates are real numbers in range (-1000,1000) with precision of 0.01. No two rings have common points.

Output file

The only number m which stands for the minimal number of shots required.

Examples:

saturn.in	saturn.out
1 0 0 0 1 0 0 0 1 0	1
2 0 0 0 1 0 0 0 1 0 0 0 0 2 0 0 0 2 0	2
3 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 1 5 5 5 5 5 6 5 6 5	2
3 0 0 0 2 0 0 0 2 0 -2 0 0 -1 0 0 -2 0 1 2 0 0 1 0 0 2 0 1	1

Source: Petrozavodsk Summer 2003. Trinity Contest, Tuesday, August 26
Author: Denis Koshman

Discuss       Submit a solution



Printable version