## 10885 - Martin the Gardener

Moderator: Board moderators

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
The points are on the same circle. But your approach is not the way to go.

kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Cho wrote:The points are on the same circle. But your approach is not the way to go.
Any hints?

Cho
A great helper
Posts: 274
Joined: Wed Oct 20, 2004 11:51 pm
Location: Hong Kong
I got the idea from misof's second reference. You don't need to understand the paper completely. From the middle of the second page to the end of the second page is enough for solving this problem. i.e. just half a page.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

### ..?

i think that misof's papper is TOO DIFFICULT to understand

and that i don't need it (because i can't make an understanding )

my idea is following :

1. all points are on a circle.
2. if coords are rational, multiplying appropriate large number, we can make them integer.
3. we can express some distances between two points on a circle with an arbitrary angle.
Sorry For My Poor English.. kp
Learning poster
Posts: 71
Joined: Tue Apr 26, 2005 1:29 am
Location: Russia
Thanks 2 all!

I got AC.

I used idea of Maehara's proof (linked by misof), just
like Cho advised mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
There's really a much simpler solution than that described in misof's reference. Here's my method:

First, I'm looking for points with rational coordinates and rational distances between any two of them, of the form:
(x_i, y_i) = (cos t_i, sin t_i), for i=1..13 (i.e. all points are lying on the unit circle.)

The distance between the i-th and j-th points is given by (after trig simplifications):
2 sin(t_i/2) cos(t_j/2) - 2 cos(t_i/2) sin(t_j/2).
Now, if I demand that all sin(t_i/2), cos(t_i/2) are rationals, then all distances and coordinates will become rational, too.

Let sin(t_i/2)=p_i/q_i (for p_i,q_i \in Z.) Then cos(t_i/2)=sqrt(q_i^2 - p_i^2)/q_i.
For cos(t_i/2) to be rational, q_i^2 - p_i^2 must be a square.
The integers p_i, q_i can be found by checking first few pythagorean triples.
The coordinates then can be easily computed by trig formulas.

To get integer coordinates and distances, I multiply each x_i, y_i by the lcm of denominators of all x_i, y_i, and then shift all points such that all coordinates become non-negative.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
Many thanks, mf.

daveon
Experienced poster
Posts: 229
Joined: Tue Aug 31, 2004 2:41 am
I just realized, I outputted negative numbers and the special corrector program still accepts this.

Is this a bug? Well, not much of a bug anyways.

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per
Well according to the previous posts "The points are on the same circle".

Therefore the circle is
(x-2)^2 + (y-3/2)^2 = (5/2)^2

But i haven't realized how that is possible because there aren