Hello.
I didn't read your code in C, but I think I know what your mistake is.
Your logic isn't correct. You say that if every two spheres intersect,
then they all have a common point. That is not true. Perhaps I will cite
an example later. Now I'll better give you an idea of the correct logic.
Imagine that you are solving the same problem, but in the 1-dimansional
space (i.e. on a straight line), where the "spheres" are just segments. In
this case your logic would have worked, and it's rather easy to prove.
But in the 2-dimensional space it isn't true already. In this case
"spheres" are circles on a plane. Of course there exist such three
2-dimensional spheres so that each two of them intersect each other, but
they all don't have a common point. But there is another statement, which
is true: if every three circles have a common point, then all the N
circles have a common point.
Next, proceed to the 3-dim. space. Here we can imagine 3, or even 4
spheres, so that every THREE of them have a common point, but still there
doesn't exist a point common for all the spheres. The correct criterion
sounds like this: if you have N>=4 spheres and every 4 of them have a
common point, then all the N spheres have a common point. See, if you
place "2" instead of "4", you'll have an incorrect statement (which is
what you supposed).
Now, the general case. Suppose everything is happening in an M-dimensoinal
space. Then we should consider every M+1 spheres, and if all these subsets
have common points, then all the N spheres have a common point. This is
true because of a theorem. The theorem is called the Helly's theorem. It's
statement is: suppose there exist N CONVEX sets (for example, spheres:) )
in an M-dimensional space. If every M+1 sets have got a non-empty
intersection, then all the N sets have got a non-empty intersection. You
can read more here:
http://en.wikipedia.org/wiki/Helly's_theorem
In case of M=1 the Helly's theorem is almost the same as the statement in
the beginning of this letter. As far as I remember, the theorem can be
proved by using the method of mathematical induction by M.
So, the problem #74 can be solved by considering all the groups consisting
of 4 spheres and checking if these groups have non-empty intersections.
And for the 4 spheres - here the combinatorics end and gemoetry begins.
For example, for every point of intersection of the surfaces of 3 spheres
you can check if this point is inside the fourth sphere. But this method
is a little wrong: for example, if all the spheres have a common center,
the surfaces of any 3 of them don't intersect... So you will also have to
consider several additional points. For example, some points from the
intersections of every two spheres' surfaces (this intersection is a
circle), and random points from the surface of every sphere. If any of
these points belongs to all the 4 spheres, then we have found a point of
intersection. Otherwise such a point doesn't exist, I suppose :)
I didn't try to ind a strict proof, because my "Accept" proved this by
experiment :) But there exist a non-strict explanation. Really, suppose
our spheres have got a non-empty intersection. This intersection is a
3-dimentional figure. And this figure has a surface. And this surface
consists of pieces of the original spheres' surfaces. This is like a
polyhedron, but its faces aren't flat :)
1) It can have only one spherical face and no edges at all. This happens
when one of the spheres lies inside all the others. In this case the
random point on the surface of this sphere is what we are looking for.
2) It can have several faces, several edges and no vertices. For example,
the intersection of 2 spheres can have 1 "edge" and 2 "faces" :). In this
case a random point from this intersection belongs to all the spheres.
3)If this "abnormal polyhedron" has at least one vertex, then this vertex
is a point where surfaces of 3 spheres intersect.
That's it. The general algo. IF you like, I can send you my code, but I
believe you will be glad to write your own.
Daniel Shved. MIPT, DREC.
dan@rt.mipt.ru