ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1312. Tray

Help me please!!! WA on test 3...
Posted by Alex[LSD] 6 Sep 2004 18:57
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.
alex[LSD], a dumb russian programmer.
Your algo is completely incorrect (+)
Posted by Dmitry 'Diman_YES' Kovalioff 6 Sep 2004 21:47
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 :)
Re: Your algo is completely incorrect (+)
Posted by Alex[LSD] 8 Sep 2004 19:09
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.
Re: Your algo is completely incorrect (+)
Posted by Dragon 3 Oct 2004 19:53
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!!
Re: Your algo is completely incorrect (+)
Posted by Kapitoshka 15 Feb 2007 12:59
1000000 1000000 250001 250001 278000 work, but 3 WA, give something interesting tests, please
Re: Your algo is completely incorrect (+)
Posted by svr 13 Sep 2007 12:08
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
Re: Your algo is completely incorrect (+)
Posted by Denis Koshman 28 Aug 2008 15:00
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.