Three in line P96191


Statement
 

pdf   zip

thehtml

Consider an n × n integer grid with exactly 2n points marked on it. Can you find three points in the same line?

Input

Input consists of several cases, each with n, followed by 2n pairs (x, y). Assume 3 ≤ n ≤ 105, that x and y are integer numbers between 1 and n, and that there are no repeated points.

Output

Print a line for every case. If there are no three (or more) points in any line, print “NO”. Otherwise, print “YES” followed by the three points that you found, in any order. If there is more than one solution, you can print any one. Follow strictly the format of the sample output.

Observation

The “large” private test cases were generated at random, by picking both x and y uniformly and independently, and descarting repeated points until having 2n in total.

Public test cases

  • Input

    3  1 1  2 2  3 3  1 3  3 1  1 2
3  1 1  2 2  3 3  1 3  3 1  1 2
4  1 1  1 2  2 3  2 4  3 1  3 2  4 3  4 4

    Output

    YES  2 2  3 3  1 1
YES  1 1  1 3  1 2
NO
    • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++