Problem Link
Author: Sahil Rajput
Tester: Sahil Rajput
Editorialist: Sahil Rajput
Difficulty
Easy
Prerequisites
Maths
Problem
The points can be vertices of regular N-polygon, if, and only if, for each pair, difference of their polar angles (as viewed from center of polygon) is a multiple of 2pi/N. All points should lie on the circle with same center as the polygon. We can locate the center of polygon/circle [but we may avoid this, as a chord (like, say, (x1,y1)-(x2,y2)) is seen at twice greater angle from center, than it is seen from other point of a cricle (x3,y3)]. There are many ways to locate center of circle, the way I used is to build midpoint perpendiculares to segments (x1,y1)-(x2,y2) and (x2,y2)-(x3,y3) in form y = ax + b and find their intersection. Formula y = ax + b has drawback that it cannot be used if line is parallel to y, possible workaround is to rotate all points by random angle (using formulae x’ = xcos(a) - ysin(a), y’ = ycos(a) + x*sin(a) ) until no segments are horizontal (and hence no perperdiculares are vertical).
After the coordinates of the center are known, we use fancy function atan2, which returns angle in right quadrant: a[i] = atan2(y[i]-ycenter, x[i]-xcenter)
Area of regular polygon increases with increasing N, so it is possible just to iterate through all possible values on N in ascending order, and exit from cycle as first satisfying N is found.
Using sin(x) is makes it easy: sin(x) = 0 when x is mutiple of pi. So, for points to belong to regular, N-polygon,
sin( N * (a[i]-a[j]) /2 )=0 because of finite precision arithmetic, fabs( sin( N * (a[i]-a[j]) /2 ) ) < eps
Solution Link