### tttt4444's blog

By tttt4444, history, 6 weeks ago,

You are given a set of points with their integer coordinates. You need to determine if there are convex quarilaterals in at most O(n^2) time.

For example: 5 2 2 5 3 8 2 7 6 4 7 Has

5 2 2 7 6 7 4 9 4 10 4 Has not

 » 6 weeks ago, # |   0 Compute the convex hull of the points. If the hull consists of at least 4 points, take any 4 from the hull. Otherwise, take any 2 points not belonging to the hull. It is guaranteed that you can form a convex quadrilateral with these 2 points and some pair of points on the hull. Complexity: $O(n logn)$.