## 10353 - Circles in Hexagon :-)

Moderator: Board moderators

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

### 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).

cyfra
Experienced poster
Posts: 144
Joined: Thu Nov 22, 2001 2:00 am
Location: Gdynia, Poland
Hi!

I got Accepted during the contest and now...

Maybe it depends on precision errors or something....

How are you counting the output ??

( my program just multiply the input by a constant

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
They must have corrected the error, but now I have AC without having resubmitted.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
what's wrong? i didn't find.
Wenyuan Dai, Shanghai Jiaotong University.

arc16
Learning poster
Posts: 62
Joined: Sun Aug 04, 2002 1:05 am
Location: Indonesia
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?

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia
Is for input 0.00000001 the-most-closed-to-real answer equal to 0.000000030230 0.000000037493? Or I'm wrong?..

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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 not very accurate. Your output must have like 9 significant digits, OR the answer must be at most 1e-9 off the correct answer (or something like that)
Is for input 0.00000001 the-most-closed-to-real answer equal to 0.000000030230 0.000000037493? Or I'm wrong?..
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...)

Helal Md. Morshed Alam
New poster
Posts: 4
Joined: Fri Oct 19, 2001 2:00 am
Contact:

### To Yarin

hi
Yarin
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...)
Can you explain it...

Thanks.

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:
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.

Mahbub
New poster
Posts: 26
Joined: Thu Aug 08, 2002 8:04 am

### 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

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

This image you've got if alpha == 54 degree (regular pentagon). So alpha must be slightly less than 54.

The same thing applies to case with eight circles.

minhaz
New poster
Posts: 5
Joined: Sat Oct 19, 2002 4:20 am
Contact:

### 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

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong
------
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