Advertisement
Guest User

Untitled

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