Posted: Sat Aug 20, 2005 8:31 pm
The points are on the same circle. But your approach is not the way to go.
Any hints?Cho wrote:The points are on the same circle. But your approach is not the way to go.
Page 2 of 2
Posted: Sat Aug 20, 2005 10:01 pm
Posted: Sun Aug 21, 2005 4:52 am
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.
..?
Posted: Sun Aug 21, 2005 3:53 pm
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.
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.
Posted: Sun Aug 21, 2005 8:55 pm
Thanks 2 all!
I got AC.
I used idea of Maehara's proof (linked by misof), just
like Cho advised
I got AC.
I used idea of Maehara's proof (linked by misof), just
like Cho advised
Posted: Sun Aug 21, 2005 11:30 pm
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.
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.
Posted: Fri Aug 26, 2005 1:09 am
Many thanks, mf.
Posted: Fri Aug 26, 2005 11:54 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.
Is this a bug?
Well, not much of a bug anyways.
Posted: Mon Aug 29, 2005 6:03 pm
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
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