Tag Archives: techgig

Techgig heckathon Launching Satellites

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:

from fractions import Fraction

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)