Is it forbidden to post WRONG programs here?
Anyways my idea is :
If there exists a solution then there exists a solution where two circles are in the corners of the rectangle. It is obvious because there is always the rightmost and the leftmost circle and we can drag them all the way to the corner.
So what I do is: I take every pair of circles, try to put each of them in every corner (16 variants for a pair of circles). Then I "erase" all the area, where the center of the 3rd circle can not be located. Firstly, the last circle (I mean it's center) has to be located inside a rectangle (W-2R)x(H-2R) whre R - is the radius. We also must exclude two circles with radii R1+R and R2+R where R1 and R2 are the radii of the already existing circles.
I store all the intersections of the 2 circles with the 4 lines (sides of the rectangle) and check all these points if they are possible positions for the last circle's center.
Please tell me where am I wrong, or give me some critical test data.
Thanks in advance.
alex[LSD], a dumb russian programmer.

The correct algo is much more complicated, and I don't want to explain it here - everyone who wants to solve this problem should manage it himself.

First try my favorite test (I am not sure your program fails on it, I just like this test):

1000000 1000000 250001 250001 278000

There IS a solution :)

Thanks, your test was really helpful. The algo is wrong, but not completely. My assumption about 2 corners was wrong, but the idea with rectangle and circles was pretty good. It just needed a recursive approach.

I was amased that your original algorithm was exactly the same as me and I also got WA on test 3! I also failed in the testdata 1000000 1000000 250001 250001 278000! Amazing!
Now I get AC and I want to say something.
You said there are two "corner-center" points on the rectangle.The fact is that there is only one!!! (I can prove , but not very strict with one part,though it seems obvious) 1000000 1000000 250001 250001 278000 is just the counterexample of "two points". Use only one corner and then deal with two groups of intersections,you will get it!!

1000000 1000000 250001 250001 278000 work, but 3 WA, give something interesting tests, please

Previouce people sad that AC algorithm much more complicated.
But really AC algorithm much more simple, pure geometric and without otimization.
One circle in corner and others have two opportunities:
to be in another corner or to be adjacent to first circle
and one of the sides of rectangle.
Thus their centers determined. After we make verification:compare distance between centers and value
R2+R3-eps. If first value greater than second- OK.
This is only verification wich made with eps.
Other verifications of placement should better make
in __int64.

Edited by author 13.09.2007 12:27

To svr. I've got AC with doubles and my default precision of 1e-8. No int64 at all.

To all: I had WA3 because of wrong code for circle removal (it remained marked as used). Try to shuffle numbers in the first test and see if something strange happens or not.