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.
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!!
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.
I think my pure-geometry based solution is correct, and I can not imagine test which it fails on, but it received WA(18). So I used some brute force optimizations and got AC, but I still don't know why was my first solution wrong...