**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 2*pi/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 = a*x + b and find their intersection. Formula y = a*x + 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’ = x*cos(a) - y*sin(a), y’ = y*cos(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**