I found this problem in a Hungarian competitive programming competition for highschool students this year. I was unable to solve it, but had no luck finding a solution afterwards - nobody I asked had a working idea.
The problem (in a nutshell):
Given a set of N points, determine if there exists a convex quad from those points (the quads corners are from the set of points), inside which no other point is contained (there is no fifth point which is inside or on the edge of the quad).
If such a quad exists, return the points (the index of the points in the input) in (any) counterclockwise order.
If no such quad exists, return 0 0 0 0.
Limits:
You get 1<=K<=10 sets with 1<=N[i]<=100 000 points with coordinates -1 000 000 <=x,y<=1 000 000
Time limit: 0.2 sec
Memory limit: 32MB
Naive solution:
For every subset with four points (N(N-1)(N-2)(N-3)/24):
Check if resulting quad is convex! If no, continue to next subset.
For every other (N-4) points:
Check if it is contained in the quad
If no point is contained, return the quad.
If no quad was returned, return "0 0 0 0"
Time complexity: O(n^5)!
Another idea (I don't think if it helps):
Do a point set triangulation, then only check neighboring triangles. Problem is, there are many possible triangulation of a set of points (see this), and we could miss a valid solution.
If one can prove that the triangulation that (maximizes angle or minimizes area or something like that) always produces a solution, this might work.
Create a Delauny triangulation. Find two adjacent triangles inside the convex hull (it means at least one of them is not located over convex hull) and report! To find more about Delauny triangulation read here.
As if there is any concave angle between four adjacent points, it will be flipped we can say every four adjacent points inside the convex hull create a convex quad.