Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- '''
- n, m = map(int, input().split())
- who_can = [[i] for i in range(n)]
- for i in range(m):
- worker = input().split()
- for j in range(n):
- if worker[j] != '0':
- who_can[j].append(i)
- '''
- def on_one_line(x1, y1, x2, y2, x3, y3):
- return (x1-x2)*x3 + (y1-y2)*y3 == 0
- def rotate(A,B,C):
- return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])
- def jarvismarch(A):
- n = len(A)
- counter = 0
- P = [i for i in range(n)]
- for i in range(1,n):
- if A[P[i]][0]<A[P[0]][0]:
- P[i], P[0] = P[0], P[i]
- H = [P[0]]
- del P[0]
- P.append(H[0])
- while True:
- right = 0
- for i in range(1,len(P)):
- if rotate(A[H[-1]], A[P[right]], A[P[i]]) < 0:
- right = i
- if P[right] == H[0]:
- break
- else:
- 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]):
- counter += 1
- H.append(P[right])
- del P[right]
- return H, counter
- n = int(input())
- A = []
- point = [0, 0]
- for i in range(n):
- A.append([int(el) for el in input().split()])
- answ, wrong = jarvismarch(A)
- print((n - 1)*(len(answ)-wrong)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement