Choose three points P74688


Statement
 

pdf   zip

html

You are given n points on the plane, no three of which are colinear. Therefore, there is always exactly one circle that passes through any three of the given points. Please choose any three points such that its corresponding circle encloses the n points.

Input

Input consists of several cases. Every case begins with n, followed by n different points, no three of which are colinear. The coordinates are integer numbers less than 105 in absolute value. Assume 3 ≤ n ≤ 5000.

Output

Print one line for every case, with three points such that their corresponding circle includes all the given points. Print, in any order and separated by one space, the index of the points (numbered from 1 to n). If there are several solutions, print any of them. If there is no solution, print “I hate geometric problems”.

Observations

  • If you use C++ floating-point numbers, in order to avoid precission issues use the long double type to perform calculations.
  • The problemsetter’s solution has cost Θ(n).
Public test cases
  • Input

    3  0 70000  70000 0  70000 70000
    5  0 3  3 0  1 1  0 -3  -3 0
    5  0 3  3 0  1 1  0 -3  -3 0
    4  -1 2  0 4  2 0  0 0
    

    Output

    3 1 2
    1 2 4
    5 4 2
    2 3 4
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Desè Concurs de Programació de la UPC - Final
    Date
    2012-09-15