## 10345 - Cricket/Football Goes Down

Moderator: Board moderators

rakeb
New poster
Posts: 42
Joined: Fri Aug 30, 2002 2:51 pm
Location: France

### 10345 - Cricket/Football Goes Down

How can i determine r3 in fig-3

Ivor
Experienced poster
Posts: 150
Joined: Wed Dec 26, 2001 2:00 am
Location: Tallinn, Estonia
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
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:

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

dwyak
New poster
Posts: 36
Joined: Sun Jul 28, 2002 5:16 am
Location: P.R.China
Contact:
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:
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
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
7th Contest of Newbies
Date: December 31st, 2011 (Saturday)
Time: 12:00 - 16:00 (UTC)
URL: http://uva.onlinejudge.org

Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:
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
Thx!!

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

Thanks again and again!!!!!
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
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:

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.

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!