10353  Circles in Hexagon :)
Moderator: Board moderators
10353  Circles in Hexagon :)
I suspect something fishy about this one, I got AC in the contest but not now. And nobody either it seems (at the moment of this writing).

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
That's not very accurate. Your output must have like 9 significant digits, OR the answer must be at most 1e9 off the correct answer (or something like that)for the 1st output i multiply the input with 3.00 and the 2nd with 3.71. I think it's right, isn't it? If so, why do i get WA?
That's wrong. The first value seems to be under the assumption that the center of the five circles are a regular polygon with 5 edges, which is not true (but it's close...)Is for input 0.00000001 themostclosedtoreal answer equal to 0.000000030230 0.000000037493? Or I'm wrong?..

 New poster
 Posts: 4
 Joined: Fri Oct 19, 2001 2:00 am
 Location: AIUB, BANGLADESH
 Contact:
To Yarin
hi
Yarin
Thanks.
Yarin
Can you explain it...That's wrong. The first value seems to be under the assumption that the center of the five circles are a regular polygon with 5 edges, which is not true (but it's close...)
Thanks.
The first thing I did when I looked at the problem was assuming that the centre of the five circles was the corners of a regular polygon with 5 sides, but that gave the wrong answer. Thus the angle between the center of leftmost circle and the topleft circle cannot be exactly 54 degrees. By testing different angles, and doing some calculations on the topright circle, you can find for each angle how big the polygon must be. Once you get the formulas correct (some sin & cos & tan or something ), a binary search of the angle will work.
The problem with 7 circles is almost the same, the angle to the topleft circle is known (since it touches the upperleft edge of the hexagon) so the binary search is performed between the topleft and top circles). Almost the same calculations otherwise.
The problem with 7 circles is almost the same, the angle to the topleft circle is known (since it touches the upperleft edge of the hexagon) so the binary search is performed between the topleft and top circles). Almost the same calculations otherwise.
Why NOT Regular Pentagon??
I am not clear why the fact is false :
that they(centers) are on regular pentagon/heptagon..they ought to be to make the figures corrrect..or else the figure is incorrec!!
Whats the tricky point here?? i cant get it..can anybody help me??
Thanks.

Mahbub
that they(centers) are on regular pentagon/heptagon..they ought to be to make the figures corrrect..or else the figure is incorrec!!
Whats the tricky point here?? i cant get it..can anybody help me??
Thanks.

Mahbub

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
tell me detail
By testing different angles, and doing some calculations on the topright circle, you can find for each angle how big the polygon must be. Once you get the formulas correct (some sin & cos & tan or something ), a binary search of the angle will work.
still i don't understand how i use bunary search and can any one give details of the formula to find relation why i have to multiply by 3 to get first output
bye
minhaz
still i don't understand how i use bunary search and can any one give details of the formula to find relation why i have to multiply by 3 to get first output
bye
minhaz

EDIT
Finally got accepted. Thanks for all your hints, guys!

(Old msg. has been deleted.)
EDIT
Finally got accepted. Thanks for all your hints, guys!

(Old msg. has been deleted.)
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org
Date: December 31st, 2011 (Saturday)
Time: 12:00  16:00 (UTC)
URL: http://uva.onlinejudge.org