for each point on plane do a binary search, if radii is too big more points will be inside. contraints are such for each point we can keep points in order of their distance. N^2 + NlogN

It is not hard to prove that we can draw such circle through any 2 points. This fact leads to evident O(n²) solution.

Here O(n) solution link

Basicly short version what I learned: 1) Answer always exists. 2) Take any segment on convex hull. Sort remaining points by angle making with this segment. Answer exactly in the middle.

of course other two points are vertices that make up this segment

Just try to 1e6 time choose three random points. And find count points in circle in O(n) time. Profit! P.S.: this solution get AC. Realy!

Let's fix one point (O) and assume it is on edge of circle. Make inversion with center O. What happens with our circle then? Circle edge becomes a line, which doesn't contain O. Inside and outside parts of circle (except O) become two parts of plane, created by line.

So we have n - 1 points (except O, we don't count it anymore), no 3 are on one line (because before inversion no 4 are on one line or on one circle), n isn't divisible by 2. We need to find a line, that divides our points in two groups of same size. Let's take points with biggest x coordinate. From such points let's take points with biggest y coordinate. Let's call it A. Then sort our points by polar angle around A and take (n - 1) / 2-th of them (B).

So, O, A', B' is answer, where A' is inverse of A, B' is inverse of B.

Complexity is or even if you find median without sorting. There can be some precision problems, though.

By the way, it looks like there is some trash at the end of third test.

Sorry for my bad English.

I am very sorry, double post.