This page is still under construction.

Parts of this page are still being built. What you see may change.

Find the Point

Time limit8sMemory limit512 MB

Summary
Given n distinct lines, find a point whose perpendicular distance to every line is equal, or report that there are many such points or none.
Level

Medium7 of 10

Topics
Geometry, Math, Implementation, Brute force
Solved
No attempts yet

Problem

We understand that reading English is a great pain to many of you. So we will keep this problem statement simple. Write a program that reports the point equally distant from a set of lines given as the input. In case of no solutions or multiple solutions, your program should report as such.

Input

The input is given in the following format:

n
x1,1 y1,1 x1,2 y1,2
x2,1 y2,1 x2,2 y2,2
...
xn,1 yn,1 xn,2 yn,2

n is the number of lines (1 ≤ n ≤ 100); (x**i,1, y**i,1) and (x**i,2, y**i,2) denote the different points the i-th line passes through. The lines do not coincide each other. The coordinates are all integers between -10000 and 10000.

Output

Print a line as follows. If there is exactly one point equally distant from all the given lines, print the x- and y-coordinates in this order with a single space between them. If there is more than one such point, just print "Many" (without quotes). If there is none, just print "None" (without quotes).

The coordinates may be printed with any number of digits after the decimal point, but should be accurate to 10-4.

Examples3

  1. Example 1

    Input
    2
-35 -35 100 100
-49 49 2000 -2000
    Expected output
    Many

  2. Example 2

    Input
    4
0 0 0 3
0 0 3 0
0 3 3 3
3 0 3 3
    Expected output
    1.5000 1.5000

  3. Example 3

    Input
    4
0 3 -4 6
3 0 6 -4
2 3 6 6
-1 2 -4 6
    Expected output
    1.0000 1.0000