Beta Round #1 C. Ancient Berland Circus

Finding a regular polygon with smallest area given three corner points A,B and C. (The Following angles are represented in radians.) First we need to find the radius of the circumscribed circle of the regular polygon, this can be done by calculating the radius of the circumscribed circle of the triangle(A,B,C). \[R=(AB*BC*AC)/(4*area(A,B,C))\] Suppose d is the size of each angle of the optimal regular polygon. Let A,B,C be the angles of AOB,BOC,AOC where O is the center point of the circumscribed circle , we know that \[A=k_1*d\] \[B=k_2*d\] \[B=k_3*d\] for \[k1,k2,k3 \in \mathbb{N}\] Note that we need d to be as large as possible in order to reduce the size of the polygon with the same circumscribed circle, which implies that d=gcd(A,B,C). Now we prove that gcd(A,B,C) is a valid solution for d. Case 1: \[gcd(k_1,k_2,k_3)=1\] In the case, d=gcd(A,B,C) Case 2: \[gcd(k_1,k_2,k_3)=k>1\] We can prove that d=gcd(A,B,C) is still a valid size of each angle of a regular polygon. Let n be the number of sizes of the polygon. \[k* \frac{2\pi}{n}=\frac{2\pi}{n-t} \] \[ \Rightarrow \frac{k}{n}=\frac{1}{n-t} \] \[ \Rightarrow t=n-\frac{n}{k} \] We need to prove that t is an integer. Note that \[k_1=k*p_1,k_2=k*p_1,k_3=k*p_1 \] for \[p1,p2,p3 \in \mathbb{N}\] Then \[d(k_1+k_2+k_3)=2\pi\] \[ \Rightarrow \frac{2\pi}{n}(k_1+k_2+k_3) = 2\pi\] \[ \Rightarrow k_1+k_2+k_3=n \] \[ \Rightarrow k(p_1+p_2+p_3)=n \] \[ \Rightarrow \frac{n}{k}=p_1+p_2+p_3 \] Thereforce \[\frac{n}{k}\] is an integer. Since n is an integer, \[t=n- \frac{n}{k}\] is an integer. In this case, we have found a d’ which is even larger than d, which implies that we should choose d’ since the area of the polygon is smaller. Now we have found d, the only thing left is to calculate the area of the regular polygon \[ polygon area=\frac{{R^2}*n*sin(d)}{2} \] where \[n=\frac{2\pi}{d}\] and we are done.