Problem E
Regular Polygon
Input: Standard Input
Output: Standard Output
A regular polygon is an n-sided
polygon in which the sides are all the same length and are symmetrically placed
about a common center (i.e., the polygon is both equiangular and equilateral).
Only certain regular polygons are "constructible" using the classical
Greek tools of the compass and straightedge. The terms equilateral triangle and
square refer to the regular 3- and 4-polygons, respectively. The picture below shows some regular
polygons with different number of sides:
Given N(0<N≤2000)
points on a particular circle, your job is to find out how many regular
polygons of different number of edges are formed by these points. For example
if you are given 100 points, then these 100 points will form a regular hexagon
if six of these 100 points are the vertices of a regular hexagon.
Input
The input file contains at most 10 sets of inputs. The description of each set is given below. The input file contains at most 20000 lines in total.
The first line of each set is an integer N(0<N≤2000) which indicates how many points are there in this set. Each of the next N lines contains two floating-point numbers, which is the Cartesian coordinate of a point (Accurate to at least nine decimal places). You can assume that all the points lie on the same circle, the center of this circle is the origin, and the coordinate of any two points will not be the same. Also assume that two points are same if their angular distance with respect to the centre of the circle is less than 10-8 radian.
Input
is terminated by a set where the value of N is zero. This set should not be
processed.
Output
For
each set of input produce one or more lines of output. First line of the output
for each set contains the serial of output as shown in the output for sample
input. Each of the next few lines will contain two integers S and F, where S
denotes the number of sides of a regular polygon and F denotes how many times
it is formed by the input points. These outputs should be sorted in ascending
order of S. The regular polygons, which are not formed by the input points,
should not be reported. For example, in case of the second sample input no
regular pentagon (5-gon) is formed, so it is not reported in the output.
Sample Input Output for Sample Input
5-1000.0000000000 0.0000000000-500.0000000000 866.0254037844500.0000000000 866.0254037844-500.0000000000 -866.02540378441000.0000000000 0.00000000006-800.0000000000 0.0000000000800.0000000000 0.0000000000-400.0000000000 692.8203230276400.0000000000 692.8203230276400.0000000000 -692.8203230276-400.0000000000 -692.8203230276
0 |
Case 1:3 1Case 2:3 2
6 1 |
Problem setter: Shahriar Manzoor
Special Thanks: Jimmy Mårdell