Advertisement
Guest User

Untitled

a guest
Jun 18th, 2019
82
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.02 KB | None | 0 0
  1. def on_one_line(x1, y1, x2, y2, x3, y3):
  2.     return (x1 - x2) * x3 + (y1 - y2) * y3 == 0
  3.  
  4.  
  5. def rotate(A, B, C):
  6.     return (B[0] - A[0]) * (C[1] - B[1]) - (B[1] - A[1]) * (C[0] - B[0])
  7.  
  8.  
  9. def jarvismarch(A):
  10.     n = len(A)
  11.  
  12.     counter = 0
  13.  
  14.     P = [i for i in range(n)]
  15.  
  16.     for i in range(1, n):
  17.         if A[P[i]][0] < A[P[0]][0]:
  18.             P[i], P[0] = P[0], P[i]
  19.  
  20.     H = [P[0]]
  21.     del P[0]
  22.     P.append(H[0])
  23.  
  24.     while True:
  25.         right = 0
  26.         for i in range(1, len(P)):
  27.  
  28.             if rotate(A[H[-1]], A[P[right]], A[P[i]]) < 0:
  29.                 right = i
  30.  
  31.         if P[right] == H[0]:
  32.             break
  33.  
  34.         else:
  35.             if on_one_line(A[H[-3]][0], A[H[-3]][1], A[H[-2]][0], A[H[-2]][1], A[H[-1]][0], A[H[-1]][1]):
  36.                 counter += 1
  37.             H.append(P[right])
  38.             del P[right]
  39.     return len(H) - counter
  40.  
  41.  
  42. n = int(input())
  43. A = []
  44. point = [0, 0]
  45. for i in range(n):
  46.     A.append([int(el) for el in input().split()])
  47. print((n - 1) * jarvismarch(A))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement