# 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, k])

d = caldistance(arr, arr, arr, arr)
count = 2
for i in range(1, len(arr) - 1):
dnew = caldistance(arr[i], arr[i], arr[i + 1], arr[i + 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(“#”)
y = s.split(“#”)
point_x.append(int(x))
point_y.append(int(y))

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

# Resolving technical problems:

We provide Remote Technical Support from Monday to Sunday, 7:00PM to 1:00 AM

Mail your problem details at writeulearn@gmail.com along with your mobile numberand we will give you a call for further details. We usually attend your problems within 60 minutes and solve it in maximum 2 days.

## 3 thoughts on “Techgig heckathon Launching Satellites”

1. shivam jindal says:

Your code in not intended properly. not able to understand the code

1. tarry says:

Now you can see some formatting

2. tarry says:

formatted code :
https://ideone.com/0zko2l

I will format it here as well when i get time

This site uses Akismet to reduce spam. Learn how your comment data is processed.