10345 - Cricket/Football Goes Down

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
rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

10345 - Cricket/Football Goes Down

Post by rakeb »

How can i determine r3 in fig-3

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia

Post by Ivor »

Radius of the circle surrounding triangle is the hint. Pick any three points that touch the circle and form a triangle. Other thing is math.

But I want to ask how to calculate r6. I seem to be having trouble. I've tried it many ways, but I still get wrong answer for r6... even for sample output.

Ivor
There is a theory which states that if ever anyone discovers exactly what the Universe is for and why it is here, it will instantly disappear and be replaced by something even more bizarre and inexplicable.

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

Post by Ivan Golubev »

May be I've did it in some perverted way but I got AC and it's enough for me ;-)

So, for case N == 6 here is the picture:
Image
We have three points with coordinates:
1: 2*s-z, s-z
2: s-z+d, -s-z
3: -z-sqrt(2)*s+d, -z-s/sqrt(2)+d

There is a linear dependency of Radius from Side length, so we can construct and solve system of three equation.

Although I've got a terrible final equation it works!

(I suspect that there's an easier way but my math isn't perfect, unfortunately...)

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak »

I did not work on the formula. I just used a bsearch to calculate r6. It's enough to get AC, and takes less work.

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela

Post by ithamar »

Can you explain a little bit about bsearch.

Which is the formula that you are bisecting. Please be a little more explicit. I solve this problem with pure Math and i want to know another approaches.

Thanxs in advance.

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:

Post by dwyak »

I used a bseach to solve the equation as Ivan Golubev said
Wenyuan Dai, Shanghai Jiaotong University.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski »

This system of three equations is system of three pitagoras equations? or is it other system ?

Greetings

PS. I found other formula, but it's not precisious ... :-(

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

Post by Observer »

I'm having trouble on calculating r6, even after reading previous post......

So could anone plz help me??!!!!

I intended to solve it by considering some angles, but in vain......
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

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

Post by Observer »

........... No reply???? .......... :cry:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil »

you are given the co-ordinates of three points on the circle (from Ivan's post) and you also know the center (0,0). so now equalize the radii you get, and you'll have 2 equations, with 2 unknowns.

good luck.

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

Post by Observer »

Thx!!

Finally I got an ACC using bisection with Ivan's equations.

Thanks again and again!!!!! :lol: :lol:
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

htl
Experienced poster
Posts: 185
Joined: Fri Jun 28, 2002 12:05 pm
Location: Taipei, Taiwan

Post by htl »

I think that the equations of Ivan are based on the assumption that the upper-right side of the lower-left square of fig.6 touches the lower-left vertex of the square in the center.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re:

Post by brianfry713 »

htl wrote:I think that the equations of Ivan are based on the assumption that the upper-right side of the lower-left square of fig.6 touches the lower-left vertex of the square in the center.
No, that is wrong, they do NOT touch, look closely at the figure and you'll see a gap.

Image
Here is a rough image of where d and z and the 3 points are.

I used Ivan's 3 points and a binary search to get an accurate enough value for the ratio of a square side to the radius. s is the side of a square, you can set it to 1 for the binary search on the radius. If you have a point x,y on the circumference of a circle you know x*x+y*y=r*r. From point 1 you can solve for z, from point 2 you can solve for d, and point 3 decides which direction to continue the binary search.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 103 (10300-10399)”