Crowded line P68571


Statement
 

pdf   zip

html

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

Input

Input consists of several cases, with only integer numbers, each one with n, followed by n different pairs (x, y). There is at least one line with at least ⌈ n/5 ⌉ of the given points. Assume 2 ≤ n ≤ 105, and that no given coordinate is larger than 106 in absolute value.

Output

For every case, print information about the line you found: The number m of all the given points that belong to your line, followed by all those m points in any order. The number m must be at least 2 and also at least ⌈ n/5 ⌉. 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++