First Question: Given n points (x, y coordinates), how will you determine they form a regular n-gon?
Required: provide an algorithm to generate a yes/no answer, provide the time order of calculation of your algorithm, code it. Provide all of these.
Here's the (psuedocode) of my solution. I'm not sure I did the Big O correctly, any comments are appreciated:
1. Traverse the list of points to determine bounds (small x, small y, big x, big y). O(n)
2. Generate midpoint from bounds. O(1)
3. Split list into two groups. Those y>midpoint.y and y<midpoint.y. O(n)
4. Sort the two lists. The "top" list with ascending X. The bottom list with descending x. O(n log n).
5. Generate expected spoke length (distance point n -> midpoint), angle (atan2). O(1)
6. Traverse the two lists, checking angle and length to match expected spoke angle and length. O(n)
O(n) + O(1) + O(n) + O(n log n) + O(n) + O(1) + O(n) = O(nlogn)
I'm not sure this is right. Is the distance formula, dot product, cross product, atan2 O(1) operations?