10353 - Circles in Hexagon :-)

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

10353 - Circles in Hexagon :-)

Post by Yarin » Wed Sep 18, 2002 12:14 am

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

Post by cyfra » Wed Sep 18, 2002 1:03 pm

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:

Post by Yarin » Wed Sep 18, 2002 2:39 pm

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:

Post by dwyak » Wed Sep 18, 2002 3:30 pm

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

Post by arc16 » Wed Sep 18, 2002 6:06 pm

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? :cry:

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

Post by Ivan Golubev » Wed Sep 18, 2002 7:27 pm

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:

Post by Yarin » Wed Sep 18, 2002 9:02 pm

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
Location: AIUB, BANGLADESH
Contact:

To Yarin

Post by Helal Md. Morshed Alam » Wed Sep 18, 2002 10:48 pm

hi
Yarin :D
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:

Post by Yarin » Thu Sep 19, 2002 1:03 am

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

Post by Mahbub » Sat Sep 21, 2002 9:16 am

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

Post by Ivan Golubev » Sat Sep 21, 2002 10:47 am

Image
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
Location: Dhaka,Bangladesh
Contact:

tell me detail

Post by minhaz » Fri Nov 08, 2002 6:36 am

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.

:roll:

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 :oops:

Observer
Guru
Posts: 570
Joined: Sat May 10, 2003 4:20 am
Location: Hong Kong

Post by Observer » Fri Jul 04, 2003 9:29 am

------
EDIT

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

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

Post Reply

Return to “Volume 103 (10300-10399)”