Guest User

Untitled

a guest
Jun 9th, 2019
200
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.01 KB | None | 0 0
  1. with open('input50.txt') as f:
  2. next(f)
  3. cord = []
  4. for line in f:
  5. line = line.split() # to deal with blank
  6. if line: # lines (ie skip them)
  7. line = [int(i) for i in line]
  8. cord.append(line)
  9.  
  10. #print(cord[0])
  11. #print(cord[1])
  12. #print(cord)
  13.  
  14.  
  15. def slope(list, a, b):
  16.  
  17. slope = 0
  18. #vertical line
  19. if(list[a][0] == list[b][0]):
  20. slope = float("inf")
  21. if(list[a][1] == list[b][1]):
  22. slope = float("-inf")
  23. else:
  24. slope = (list[b][1] - list[a][1])/(list[b][0] - list[a][0])
  25.  
  26. return slope
  27.  
  28. def compareTo(list, a, b):
  29. #return less if a < b
  30. if((list[a][1] <= list[b][1]) and (list[a][0]<list[b][0])):
  31. return 'less'
  32.  
  33. def slopeOrder(list, a, b, c):
  34. #return less if slope of b is less than c taking a as refernce point
  35.  
  36. if(slope(list, a, b) < slopeTo(list, a, c)):
  37. return 'less'
  38. if(slope(list, a, b) == slopeTo(list, a, c)):
  39. return 'equal'
  40.  
  41.  
  42.  
  43. def BruteCollinearPoint(list):
  44. #examines 4 points at a time and checks whether they all lie on the same line segment, returning all such line segments
  45. #check whether the three slopes between p and q, between p and r, and between p and s are all equal. --> O(n^4)
  46. for i in range(0,len(list)):
  47. for j in range(i+1, len(list)):
  48. for k in range(j+1, len(list)):
  49. for l in range(k+1, len(list)):
  50. if ((slope(list , i ,j) == slope(list, i, k)) and (slope(list , i ,j) == slope(list, i, l))):
  51. print("collinear points are ")
  52. print(list[i] , list[j] ,list[k] , list[l])
  53. return
  54.  
  55. #BruteCollinearPoint(cord)
  56.  
  57. def FastCollinearPoint(list):
  58.  
  59. slope_array = list
  60.  
  61. for i in range(len(list)):
  62.  
  63. ss = slope(list, 0 ,i)
  64. print(ss)
  65. slope_array[i][0] = ss
  66.  
  67.  
  68.  
  69. #sort using any sort
  70. #slope_array.sort()
  71. #print(slope_array)
  72.  
  73.  
  74.  
  75.  
  76.  
  77. FastCollinearPoint(cord)
Add Comment
Please, Sign In to add comment