Question: https://codility.com/demo/take-sample-test/polygon_concavity_index/

Question Name: Polygon-Concavity-Index or PolygonConcavityIndex

Thanks to Robert Sedgewick, the Youtube video (Algorithms, Part I – Convex Hull) tells everything about this problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
def _IsClockwise(point_A, point_B, point_C): ''' Return the direction from points A -> B -> C. ''' result = (point_B.x - point_A.x) * (point_C.y - point_A.y) - (point_B.y - point_A.y) * (point_C.x - point_A.x) # The direction of a->b->c is: if result > 0: return 1 # counter-clockwise elif result < 0: return -1 # clockwise else: return 0 # a staight line def solution(A): ''' The solution refers to: https://www.youtube.com/watch?v=0HZaRu5IupM ''' # Find the lowest point(s) in y-axis. lowest_y = A[0].y lowest_y_index = [] for i in xrange(len(A)): if A[i].y < lowest_y: lowest_y = A[i].y lowest_y_index = [i] elif A[i].y == lowest_y: lowest_y_index.append(i) else: continue # Find a point, which is not the lowest in y-axis and immediately # after a lowest-in-y-axis point. start_point = lowest_y_index[0] lowest_y_array = [False] * len(A) for i in lowest_y_index: lowest_y_array[i] = True while lowest_y_array[start_point] == True: start_point = (start_point + 1) % len(A) start_point = (start_point - 1 + len(A)) % len(A) # Re-organize the points so that, it is easier to check every three # consecutive points in one loop (without module operation %). rotated_A = A[start_point : ] + A[ : start_point] # We find the start point such that, the direction is non-zero. direction = _IsClockwise(rotated_A[-1], rotated_A[0], rotated_A[1]) extened_A = rotated_A + rotated_A[:2] for i in xrange(len(A)): temp = _IsClockwise(extened_A[i], extened_A[i+1], extened_A[i+2]) if temp * direction < 0: # Compute the original index and return return (i + 1 + start_point)%len(A) # Every point is on the convex hull. return -1 |

Hi! I do not understand how exactly to do it in languages that can have arithmetic overflow in functions like _IsClockwise. Levi

hmm~ Good catch! Python does not have the overflow issue. And Java has BigInteger/BigDecimal. For C/C++, you can have a similar big number class or use more if-else in overflow detection.