### DELETED02's blog

By DELETED02, 9 years ago, translation, , Good day! Here, I wrote another of problem "С" from CBR #1

First find the radius of the circle of our triangle, this is the radius of the desired n-gon. Denote the radius of the circle through RThen R = abc / 4S,  where a, b, c sides of the triangl, Sarea of a triangleWe find all the angles of this triangle and denote them as A, B, CThe angles A, B, C can be found on this formula:
A = acos((b2 + c2 - a2) / (2bc)))B, C computes similarlyNow we find n.It here so: n = pi / gcd(A, B, C)Now we know R and n, with which we can find the area n-gon by this formula: n / 2 * R2 * sin(2pi / n).

Note that gcd (A, B, C) = gcd (gcd (A, B), C)
and the function gcd (x, y) can be calculated as follows:

double gcd(double x, double y) {
while (fabs(x) > eps && fabs(y) > eps) {
if (x > y)
x -= floor(x / y) * y;
else
y -= floor(y / x) * x;
}
return x + y;
}

//eps = 1e-4 Tutorial of Codeforces Beta Round #1  Comments (16)
 » Need the explanation of formula 1. n = pi / gcd(A, B, C) and2. n ploygon area = n / 2 * R2 * sin(2pi / n)
•  » » 5 years ago, # ^ | ← Rev. 2 →   I couldn't understand The first formula but I understood the second one, The condition in the problem is somewhat like this. Here we can see that a n sided regular polygon is composed of n triangles all of which have a vertex at the center of the circle. So to find the total area we select one of the triangle's like this and find it's area and multiply it by n. We know the central angle of each such triangle is and from the figure we see that OF = (R cos ( ))and DF = (R sin ( )) also DE = 2Rsin ( ) So Area of ODE is ( ) = (R cos ( )) (2Rsin ( )) = ( ) sin ( )Total area = ( ) sin ( )The images were made with MS Paint so I apologize for the quality. I followed whatever the editorial said and got AC 9274841.
•  » » 3 years ago, # ^ | ← Rev. 3 →   Divide the polygon into n triangles and every triangles area is 1/2*r*r*sinA(A=2*pi/n).
•  » » the first formula is because all the angles formed by taking any pair of vertices to the center is integral multiple of 360/n. As we are interested to find out minimum 'n'(minimum 'n' is because the area of a regular polygon is a monotonic increasing function to its n) it is sufficient to calculate gcd of 3 angles and divide it with pi.
 » I try to make A=2*sin(a/2/R) and so do B C, then n=2*PI/gcd(A,gcd(B,C)); but this only work till test 16 change to the way you write, it accepted , can anyone explain it?
 » 5 years ago, # | ← Rev. 2 →   .
•  » » You should not judge one who made a mistake ( to your mind ) almost 2 years ago. Use time machine !
 » Eventually solve this problem，thanks！
 » How do you prove that N = PI / (gcd(A, B, C)) ?
•  » » 3 years ago, # ^ | ← Rev. 2 →   2 * Pi / N is an angle from the center of the сircumscribed circle between two closest vertices of desired polygon. Then angles from the center between two vertices of triangle will be a * (2 * PI / N), b * (2 * PI / N) and c * (2 * PI / N), where a + b + c = N. Now let's notice, that the angles of our triangle (A, B, C) are inscribed angles of the сircumscribed circle. Therefore A = a * (PI / N), etc. Therefore gcd(A, B, C) = PI / N. It is also true if gcd(a, b, c) > 1`, because it is beneficial to take the least N.
•  » » » Thanks :)
•  » » » » hi i couldn't understand n? what is it n?
•  » » » » » 14 months ago, # ^ | ← Rev. 2 →   N is the number of sides of the polygon.The angle at the centre of a circle is twice any angle at the circumference subtended by the same arc.https://www.khanacademy.org/math/geometry/hs-geo-circles/hs-geo-inscribed-angles/a/inscribed-and-central-angles-proof
 » can someone help me with the concept of epsilon in finding the gcd. Why do most of the accepted answers have it as 10^-4 . when i reduce it to 10^-5 , i get incorrect answer. Can someone tell me how did we decide this value because i think that lesser the value of eps meant a more precise answer??
•  » » I used this code (https://www.geeksforgeeks.org/program-find-gcd-floating-point-numbers/) and found that even a value of 1e-2 for epsilon gives a correct answer.
 » How is being n calculated here? n=PI/gcd(a,b,c)?