Algo which I wrote is O(n*logn) but also I know O(n) one.

Try to choose one point which will be on the circle. O(1)
Than try to choose another one point which will be on the circle. O(n*logn) or O(n)
Finally build circle by these two points. O(n)

PS: I used such two points that all other points are at one side of the line which contains these two points.

I not understand why your algo is right. Maybe we'll discuss some questions by e-mail. Mine is victorbarinov@ua.fm
Thanks!

My simple linear solution uses Inversive geometry.

1. Inverse plane with respect to one of points (let it is A). O(n).
2. Chose another (not A) most left point (let it is B). O(n).
3. Sort all points without A and B with respect to B by polar angle and chose middle (let it is C). We want to get exactly one element on middle place, so I used std::nth_element which work O(n).
4. Output A, B, C. O(1).

I can guarantee that the above algorithm is working. I came up with a similar algorithm :)

Thx @Ripatti [Ufa].
A solve with O(n) , got AC 0.001s.

Hint for others:
1. did not need any math functions, like  acos, atan.  use simple vector multiplications.
2. calc cos(v[i]) , i>2.  values before sorting.
3. use std::nth_element
4. if need more speed, use buffered i/o.

Good Luck!!