Advertisement
Guest User

Untitled

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