Techgig heckathon Launching Satellites

Satellite placed in space is having some X and Y  axis coordinates . Satellites are placed in straight line and each having equal distance with each other. Find a path having maximum number of satellites in a single line. These lines should have minimum 3 satellites.

Input format :

Argument 1 : rows in grid denoted by R

Argument 2 : cols in grid denoted by C

Argument 3 : array of positions of each satellite seperated by # sign.

Constrains :

R >= 1

C  <= 5000

Output format

Number of satellites along a path in a single line if there exist at-least any 1 path else return 0.

Sample test cases :

Sample input:

100

100

3

1#1

1#100

100#1

Sample Output 

0

Solution in  python:

def calslope(x1, y1, x2, y2):
  slope_string = ””

  if (x2 - x1 == 0):
    slope_string = ’INF’
elif(y2 - y1 == 0):
  slope_string = ’0′
else :
  frac = Fraction(y2 - y1, x2 - x1)

sign = ’+’
  if frac.numerator < 0:
  sign = ’-‘

  slope_string = sign + ‘ | ’+str(abs(frac.numerator)) + ‘ | ’+str(abs(frac.denominator))
return slope_string

def caldistance(x1, y1, x2, y2):

  return str(((y2 - y1) * (y2 - y1)) + ((x2 - x1) * (x2 - x1)))

def calintercepts(x1, y1, x2, y2):
  s_y = y2 - y1
s_x = x2 - x1
intercept_string = ”

  if s_y == 0:
  intercept_string = ’+ | ’+str(abs(y1)) + ‘#INF’
if y1 < 0:
  intercept_string = ’- | ’+str(abs(y1)) + ‘#INF’

elif s_x == 0:
  intercept_string = ’INF# + ’ +str(abs(x1))
if x1 < 0:
  intercept_string = ’INF# - ‘ +str(abs(x1))

else :
  slope = Fraction(s_y, s_x)
c = Fraction((slope.denominator * y1 - slope.numerator * x1), slope.denominator)
y_intercept = c
x_intercept = Fraction(-1 * c.numerator * slope.denominator, c.denominator * slope.numerator)

y_int_string = ”
  sign = ‘+’
  if y_intercept.numerator < 0:
  sign = ’-‘
  y_int_string = sign + ‘ | ’+str(abs(y_intercept.numerator)) + ’ | ’+str(abs(y_intercept.denominator))

x_int_string = ”
  sign = ‘+’
  if x_intercept.numerator < 0:
  sign = ’-‘
  x_int_string = sign + ‘ | ’+str(abs(x_intercept.numerator)) + ’ | ’+str(abs(x_intercept.denominator))

intercept_string = y_int_string + ‘#’ +x_int_string
return intercept_string

def parsepoints(n, point_x, point_y):

  #for i in range(0, n): #print point_x[i], point_y[i]

MAP = {}
for i in range(0, n - 1):
  for j in range(i + 1, n):
  a = point_x[i]
b = point_y[i]
c = point_x[j]
d = point_y[j]

mapstring = calslope(a, b, c, d) + ‘#’ +caldistance(a, b, c, d) + ‘#’ +calintercepts(a, b, c, d)

if mapstring in MAP:
  MAP[mapstring].append(i)
MAP[mapstring].append(j)
else :
  MAP[mapstring] = []
MAP[mapstring].append(i)
MAP[mapstring].append(j)
ans = 2
for ms in MAP:
  points = MAP[ms]
points = list(set(points))# print len(points)
arr = list()
for i in range(0, len(points)):
  p = list()
p.append(point_x[points[i]])
p.append(point_y[points[i]])
arr.append(p)

arr.sort(key = lambda k: [k[0], k[1]])

d = caldistance(arr[0][0], arr[0][1], arr[1][0], arr[1][1])
count = 2
for i in range(1, len(arr) - 1):
  dnew = caldistance(arr[i][0], arr[i][1], arr[i + 1][0], arr[i + 1][1])
if dnew == d:
  count = count + 1
ans = max(ans, count)
else :
  d = dnew
count = 2
print ans
if ans > 3:
  return ans
else :
  return 0
return ans

n = raw_input()
point_x = list()
point_y = list()
for i in range(0, int(n)):
  s = raw_input()
x = s.split(“#”)[0]
y = s.split(“#”)[1]
point_x.append(int(x))
point_y.append(int(y))

print parsepoints(int(n), point_x, point_y)