Crowded line P68571


Statement
 

pdf   zip

You are given nn points on the plane. You have the guarantee that there exists at least one line that contains at least 20%20\% of the nn given points. Find any such line.

Input

Input consists of several cases, with only integer numbers, each one with nn, followed by nn different pairs (x,y)(x, y). There is at least one line with at least n/5\lceil n/5 \rceil of the given points. Assume 2n1052 \le n \le 10^5, and that no given coordinate is larger than 10610^6 in absolute value.

Output

For every case, print information about the line you found: The number mm of all the given points that belong to your line, followed by all those mm points in any order. The number mm must be at least 2 and also at least n/5\lceil n/5 \rceil. If there is more than one possible line, choose any one. Follow strictly the format of the sample output.

Public test cases
  • Input

    4  0 0  0 -1  -1 0  -1 -1
    3  999991 999992  999992 999993  999993 999994
    11  7 0  7 2  -7 2  6 4  -6 4  5 5  -5 5  3 6  -3 6  0 7  3 3
    

    Output

    2  0 -1  -1 0
    3  999991 999992  999992 999993  999993 999994
    3  7 2  -5 5  3 3
    
  • Information
    Author
    Ivan Geffner
    Language
    English
    Official solutions
    C++
    User solutions
    C++