10439 - Temple of Dune

[Bistromath]

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

[gvcormac]

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]

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]

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]

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

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]

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]

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

7 does not divide 360

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]

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 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]

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]

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]

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]

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]

Thank you

I got AC.

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]

as topic

[Dominik Michniewski]

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