Advertisement
Guest User

Untitled

a guest
Jun 26th, 2017
67
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 1.85 KB | None | 0 0
  1. def rotate(A,B,C):
  2.   return (B[0]-A[0])*(C[1]-B[1])-(B[1]-A[1])*(C[0]-B[0])
  3.  
  4. def intersect(A,B,C,D):
  5.   return rotate(A,B,C)*rotate(A,B,D)<=0 and rotate(C,D,A)*rotate(C,D,B)<=0
  6.  
  7. def pointloc(P,A):
  8.   n = len(P)
  9.   if rotate(P[0],P[1],A)<0 or rotate(P[0],P[n-1],A)>0:
  10.     return False
  11.  
  12. def inner(P,A):
  13.     if (P[0][0] == A[0] and P[0][1] == A[1]):
  14.         return False
  15.     ret = pointloc(P,A)
  16.     if (ret == False):
  17.         return False
  18.     n = len(P)
  19.     p, r = 1, n-1
  20.     if (rotate(P[0],P[1],A)==0): return False
  21.     if (rotate(P[0],P[n-1],A)==0): return False
  22.     while r-p>1:
  23.         q = (p+r)/2
  24.         if rotate(P[0],P[q],A)<=0: r = q
  25.         else: p = q
  26.     return not intersect(P[0],A,P[p],P[r])
  27.  
  28. def grahamscan(A):
  29.   n = len(A)
  30.   P = range(n)
  31.   for i in range(1,n):
  32.     if A[P[i]][0]<A[P[0]][0]:
  33.       P[i], P[0] = P[0], P[i]
  34.   for i in range(2,n):
  35.     j = i
  36.     while j>1 and (rotate(A[P[0]],A[P[j-1]],A[P[j]])<0):
  37.       P[j], P[j-1] = P[j-1], P[j]
  38.       j -= 1
  39.   S = [P[0],P[1]]
  40.   for i in range(2,n):
  41.     while rotate(A[S[-2]],A[S[-1]],A[P[i]])<0:
  42.       del S[-1]
  43.     S.append(P[i])
  44.   return S
  45.  
  46. 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]]
  47. index = grahamscan(mass)
  48. P = []
  49. for i in range(0, len(index)):
  50.     P.append(mass[index[i]])
  51. print(P)
  52. inc=0
  53. for i in range(-100,100):
  54.     for j in range(-100,100):
  55.         if (inner(P,[i,j]) == True):
  56.             print([i,j])
  57.             inc = inc + 1
  58. print(inc)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement