10439 - Temple of Dune

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Bistromath
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( ( a2-1), (a3-a1))
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.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Re: 10439 - Temple of Dune

Bistromath wrote:I can't figure why i always get WA.

4. result = gcd/(2*PI)

Thanks
Can you prove that result is an integer?

Andrey Mokhov
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.

Bistromath
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

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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.)

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

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France
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

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:

Consider a polygon with 360 vertices at integral
angles.

a1 = 0
a2 = 7
a3 = 28

gcd(a2-a1, a3-a1) = 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

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
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.

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

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France
To gvcormac

Thanks for your suggestions, i have finally solved the problem.
As you suggest, GCD is not necessary ( and subject to precision errors) as we now the maximum number of vertices.

Many thanks for your help

cytse
Learning poster
Posts: 67
Joined: Mon Sep 16, 2002 2:47 pm
Location: Hong Kong
Contact:
Bistromath wrote: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
angle at center == 2 x angle at circumference

Seokchan
New poster
Posts: 3
Joined: Thu Feb 06, 2003 3:28 pm
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.

Bistromath
New poster
Posts: 16
Joined: Fri Oct 11, 2002 11:03 pm
Location: France
Seokchan wrote: I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.
In my accepted solution, i have used the following function to check if a is a multiple of b :

[cpp]
inline bool IsAMultipleOf( double num, double div )
{
const double l = num/div ;
double dl = fabs(l-(int)(l+0.5)) ;
return ( dl < 1E-3 ) ;
}
[/cpp]

Hope this helps

Seokchan
New poster
Posts: 3
Joined: Thu Feb 06, 2003 3:28 pm
Thank you

I got AC.

Bistromath wrote:
Seokchan wrote: I wonder my algorithm has some precision problem, but I don`t know how to avoid that problem.
In my accepted solution, i have used the following function to check if a is a multiple of b :

[cpp]
inline bool IsAMultipleOf( double num, double div )
{
const double l = num/div ;
double dl = fabs(l-(int)(l+0.5)) ;
return ( dl < 1E-3 ) ;
}
[/cpp]

Hope this helps

magicalan
New poster
Posts: 3
Joined: Wed Jan 29, 2003 1:52 pm
Location: Hong Kong

are there any method to find out the angles quickly ?

as topic
ALAN LEE

Dominik Michniewski
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 (cross-vector? 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)