Given N points on a circle, centered at the origin, design an algorithm that determines whether there are two points that are antipodal, i.e., the line connecting the two points goes through the origin. Your algorithm should run in time proportional to N log N.
Algorithm :
1. Sort the points into increasing order by x
2. Set i = 0 and j = n-1
3. Loop while i < j:
if x[i] + x[j] < 0, increment i
else if x[i] + x[j] > 0, decrement j
else if y[i] + y[j] == 0 return TRUE
4. return FALSE
Algorithm :
1. Sort the points into increasing order by x
2. Set i = 0 and j = n-1
3. Loop while i < j:
if x[i] + x[j] < 0, increment i
else if x[i] + x[j] > 0, decrement j
else if y[i] + y[j] == 0 return TRUE
4. return FALSE
No comments:
Post a Comment