10439  Temple of Dune
Moderator: Board moderators

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
10439  Temple of Dune
I can't figure why i always get WA. I get correct results for sample cases
Is there any special test case with this problem ?
I think my algorithm is good :
1. find the circle through the 3 points
2. find three angles a1, a2, a3 (sorted)
3. compute the gcd( ( a21), (a3a1))
4. result = (2*PI)/gcd
In step 3, i use an epsilon. I have tried many values, without success
Any help appreciated
Thanks
Is there any special test case with this problem ?
I think my algorithm is good :
1. find the circle through the 3 points
2. find three angles a1, a2, a3 (sorted)
3. compute the gcd( ( a21), (a3a1))
4. result = (2*PI)/gcd
In step 3, i use an epsilon. I have tried many values, without success
Any help appreciated
Thanks
Last edited by Bistromath on Wed Feb 05, 2003 6:59 pm, edited 1 time in total.
Re: 10439  Temple of Dune
Can you prove that result is an integer?Bistromath wrote:I can't figure why i always get WA.
4. result = gcd/(2*PI)
Thanks

 Experienced poster
 Posts: 128
 Joined: Fri Nov 15, 2002 7:45 am
 Location: Kyrgyzstan
By the way their is a nice trick.
In fact you needn't the circle through three points.
You can get the three angles of the triangle made by the three vertices and then multiply them by 2  and you will get your a1,a2,a3!!
So maybe that won't help but it reduces code and floating point errors as there are little floating point operations.
Good luck!
Andrey.
In fact you needn't the circle through three points.
You can get the three angles of the triangle made by the three vertices and then multiply them by 2  and you will get your a1,a2,a3!!
So maybe that won't help but it reduces code and floating point errors as there are little floating point operations.
Good luck!
Andrey.

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
To gvcormac :
obiously, the gcd i compute is a floating number.
I cast to integer like that :
[cpp]
const double v = GCD( theta1, theta2) ;
const int verticeCount = (int)(0.1 + (2*PI)/v) ;
[/cpp]
I think this is correct
to Andrey :
the angles i need are the angle of the vectors from center of circle to each of the 3 vertices.
i don't see any relation with the 3 angles of the triangles
Thanks for ur help
obiously, the gcd i compute is a floating number.
I cast to integer like that :
[cpp]
const double v = GCD( theta1, theta2) ;
const int verticeCount = (int)(0.1 + (2*PI)/v) ;
[/cpp]
I think this is correct
to Andrey :
the angles i need are the angle of the vectors from center of circle to each of the 3 vertices.
i don't see any relation with the 3 angles of the triangles
Thanks for ur help
Let me rephrase my comment.
Are you sure that v divides 2*PI?
(Hint: it doesn't. This has nothing to do
with floating point representation.)
Are you sure that v divides 2*PI?
(Hint: it doesn't. This has nothing to do
with floating point representation.)
Bistromath wrote:To gvcormac :
obiously, the gcd i compute is a floating number.
I cast to integer like that :
[cpp]
const double v = GCD( theta1, theta2) ;
const int verticeCount = (int)(0.1 + (2*PI)/v) ;
[/cpp]
I think this is correct
to Andrey :
the angles i need are the angle of the vectors from center of circle to each of the 3 vertices.
i don't see any relation with the 3 angles of the triangles
Thanks for ur help

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
Allow me please to use degrees instead of radians.
Consider a polygon with 360 vertices at integral
angles.
a1 = 0
a2 = 7
a3 = 28
gcd(a2a1, a3a1) = 7
7 does not divide 360
Consider a polygon with 360 vertices at integral
angles.
a1 = 0
a2 = 7
a3 = 28
gcd(a2a1, a3a1) = 7
7 does not divide 360
Bistromath wrote:I do not understand why v shouldn't divide 2*PI (because we are trying to find a regular polygon).
In all sample cases, 2*PI was a multiple of v (+/ epsilon)
Could u please give some cases where this is not true.
Thanks
I have given a counterexample.
I would suggest however that you not look at the
counterexample, but instead try to prove that
your assertion below is true.
Often in attempting to prove something you come
up with a counterexample.
I would suggest however that you not look at the
counterexample, but instead try to prove that
your assertion below is true.
Often in attempting to prove something you come
up with a counterexample.
Bistromath wrote:I do not understand why v shouldn't divide 2*PI (because we are trying to find a regular polygon).
In all sample cases, 2*PI was a multiple of v (+/ epsilon)
Could u please give some cases where this is not true.
Thanks

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
I think my algorithm for this problem is simple and there is no exceptional cases, but I failed to got AC.
My algorithm is :
1. find angles.
2. check whether angles are multiple of (2*Pi/n) (n = 3~200)
(I thought a is multiple of b, if ((a/b)  floor(a/b) < epsilon). )
I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.
My algorithm is :
1. find angles.
2. check whether angles are multiple of (2*Pi/n) (n = 3~200)
(I thought a is multiple of b, if ((a/b)  floor(a/b) < epsilon). )
I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.

 New poster
 Posts: 16
 Joined: Fri Oct 11, 2002 11:03 pm
 Location: France
In my accepted solution, i have used the following function to check if a is a multiple of b :Seokchan wrote: I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.
[cpp]
inline bool IsAMultipleOf( double num, double div )
{
const double l = num/div ;
double dl = fabs(l(int)(l+0.5)) ;
return ( dl < 1E3 ) ;
}
[/cpp]
Hope this helps
Thank you
I got AC.
I got AC.
Bistromath wrote:In my accepted solution, i have used the following function to check if a is a multiple of b :Seokchan wrote: I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.
[cpp]
inline bool IsAMultipleOf( double num, double div )
{
const double l = num/div ;
double dl = fabs(l(int)(l+0.5)) ;
return ( dl < 1E3 ) ;
}
[/cpp]
Hope this helps

 Guru
 Posts: 834
 Joined: Wed May 29, 2002 4:11 pm
 Location: Wroclaw, Poland
 Contact:
use formula, which compute angle between vectors:
alfa = acos( ABoAC / (sqrt(AB) * sqrt(AC)) );
ABoAC  scalar multiply of vectors (crossvector? I don't remember exactly name)
AC  length of vector with endings in A and C, similar AB
Dominik
alfa = acos( ABoAC / (sqrt(AB) * sqrt(AC)) );
ABoAC  scalar multiply of vectors (crossvector? I don't remember exactly name)
AC  length of vector with endings in A and C, similar AB
Dominik
If you really want to get Accepted, try to think about possible, and after that  about impossible ... and you'll get, what you want ....
Born from ashes  restarting counter of problems (800+ solved problems)
Born from ashes  restarting counter of problems (800+ solved problems)