Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- def rotate(A,B,C):
- return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])
- def intersect(A,B,C,D):
- return rotate(A,B,C)*rotate(A,B,D)<=0 and rotate(C,D,A)*rotate(C,D,B)<=0
- def pointloc(P,A):
- n = len(P)
- if rotate(P[0],P[1],A)<0 or rotate(P[0],P[n-1],A)>0:
- return False
- def inner(P,A):
- if (P[0][0] == A[0] and P[0][1] == A[1]):
- return False
- ret = pointloc(P,A)
- if (ret == False):
- return False
- n = len(P)
- p, r = 1, n-1
- if (rotate(P[0],P[1],A)==0): return False
- if (rotate(P[0],P[n-1],A)==0): return False
- while r-p>1:
- q = (p+r)/2
- if rotate(P[0],P[q],A)<=0: r = q
- else: p = q
- return not intersect(P[0],A,P[p],P[r])
- def grahamscan(A):
- n = len(A)
- P = 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]
- for i in range(2,n):
- j = i
- while j>1 and (rotate(A[P[0]],A[P[j-1]],A[P[j]])<0):
- P[j], P[j-1] = P[j-1], P[j]
- j -= 1
- S = [P[0],P[1]]
- for i in range(2,n):
- while rotate(A[S[-2]],A[S[-1]],A[P[i]])<0:
- del S[-1]
- S.append(P[i])
- return S
- mass = [[-28,20],[-19,32],[57,-11],[52,-94],[22,-51],[-89,92],[-45,-59],[-14,-4],[74,26],[79,82],[58,-55],[95,-80],[17,-96],[89,71],[-75,10],[55,-53],[74,56],[-28,49],[-21,85],[75,-92],[73,-79],[-96,9],[-48,-82],[-57,44],[54,64],[-88,-66],[74,82],[-26,76],[96,86],[68,73],[-1,-21],[40,-51],[-57,62],[-87,-46],[21,53],[52,31],[73,77],[76,65],[-25,58],[-39,95],[58,-70],[41,-38],[89,-7],[-6,63],[8,-98],[-60,-43],[48,-37],[-24,-72],[88,-13],[97,57],[-10,71],[64,-98]]
- index = grahamscan(mass)
- P = []
- for i in range(0, len(index)):
- P.append(mass[index[i]])
- print(P)
- inc=0
- for i in range(-100,100):
- for j in range(-100,100):
- if (inner(P,[i,j]) == True):
- print([i,j])
- inc = inc + 1
- print(inc)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement