ECOO '19 R2 P2 - Pizza

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 13.0s
Memory limit: 512M

Problem type

Alice and Bob like to eat lunch at Polypizza, a hip new pizzeria that lets you choose the shape of your pizza. Whenever they come to Polypizza, Alice and Bob order a single pizza in the shape of a polygon that they like on that day. Since they want to share the pizza equally, they want the pizza to be symmetrical. They have asked for your help in determining how many reflective symmetries their pizza has (as they are too busy choosing the shapes of their toppings).

Alice and Bob's pizza has N distinct vertices. For any pair of two vertices A and B, the pizza is said to have reflectional symmetry over the line L passing through A and B if for every vertex C, there exists a different vertex located at the reflection of C over L. Two symmetries are considered different if their unordered pair of points \{A, B\} is different.

Input Specification

The input will contain 10 datasets. Each dataset begins with a single integer N (3 \le N \le 5\,000), the number of vertices that the pizza has. The next N lines each contain two integers X_i, Y_i (0 \le X_i, Y_i \le 10^6) which describe the vertices in clockwise order. The pizza is guaranteed to not have any intersecting edges.

For the first 3 datasets, N \le 50.
For the first 7 datasets, N \le 500.

Output Specification

For each dataset, output the number of reflectional symmetries that the pizza has.

Sample Input (Two Datasets Shown)

0 0
1 1
1 2
2 0
0 0
0 1
1 1
1 0

Sample Output


Educational Computing Organization of Ontario - statements, test data and other materials can be found at


There are no comments at the moment.