Convex Regular Polygon

Time limit1sMemory limit128 MB

Summary
Given three vertices of some convex regular polygon, compute the minimum number of sides that polygon could have.
Level

Medium6 of 10

Topics
Geometry, Math, Number theory
Solved
No attempts yet

Problem

A convex regular polygon is a polygon whose sides all have equal length and whose interior angles are all equal, with every interior angle smaller than 180∘180^\circ. For example, a square is a convex regular polygon.

You are given the coordinates of three distinct vertices of some convex regular polygon RR. Among all convex regular polygons that have these three points as vertices, determine the smallest possible number of vertices.

Input

The input consists of several test cases. Each test case is given on three lines; each line contains one vertex (xi,yi)(x_i, y_i) of the convex regular polygon RR (−104≤xi,yi≤104-10^4 \le x_i, y_i \le 10^4).

Each coordinate is accurate to within 10−610^{-6} of its true value (the difference from the exact coordinate is at most 10−610^{-6}). The distance between any two points is always at least 11, and RR has at most 10001000 vertices.

The last line of the input is END, which marks the end of the input.

Output

For each test case, print on its own line the minimum possible number of vertices of the convex regular polygon RR.

Examples2

  1. Example 1

    Input
    -1385.736326 -146.954822
    430.000292 -2041.361203
    1162.736034 478.316025
    0.000000 4147.000000
    -4147.000000 0.000000
    0.000000 -4147.000000
    END
    
    Expected output
    3
    4
    
  2. Example 2

    Input
    1000.000000 0.000000
    0.000000 1000.000000
    -1000.000000 0.000000
    END
    
    Expected output
    4