tttt4444's blog

By tttt4444, history, 6 weeks ago, In English

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

Thank you for your help!

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by tttt4444 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.google.com Try this one, works most of times if you're the same color as me

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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)$$$.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Check if there i s a conv ex quadrilateral from a given set of points