According to the time limit and N size we cannot use O(N^3). Therefore it should be O(N^2) or O(N^2*lnN). What's the trick? O(N^2) - it's just to select two points. How to find other three quickly? Perhaps they should be chosen randomly? Or maybe we should use Graham scan as many times as possible, to see what we get?

Is there really such an algo? You don't have to tell me the idea, just say that there is such an algo...

Theoretically, O(C(5,N)), but in a practice - O(1) :)

I thought about this problem. It can be proven, that you can build a polygon with 4 vertices from any 5 that don't lie on the same line (that is one of the statements). How many vertices does one need to build a 5 vertex convex polygon (I think about 10 or 15)...

There exists an algorithm with O(N*h) complexity...

I have O(1) complexity