Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def on_one_line(x1, y1, x2, y2, x3, y3):
- if(x1 == x2) and (x2 == x3):
- return 1 == 1
- if (y1 == y2) and (y2 == y3):
- return 1 == 1
- return (x3 - x1)/(x2 - x1) == (y3 - y1)/(y2 - y1)
- 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:
- H.append(P[right])
- if len(H) > 2:
- 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]):
- counter += 1
- del P[right]
- return len(H) - counter
- n = int(input())
- A = []
- for i in range(n):
- A.append([int(el) for el in input().split()])
- print((n - 1) * jarvismarch(A))
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement