@Kunal. Step 3 is inadequate. If the search in step 2 returns true,
then you still have to check to see if the y-coordinates are negatives
of each other.
But you really don't have to do a binary search in step 2; you can
search from both ends of the array, as follows.
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
You can do the inequality and equality tests with a tolerance if
desired.
Dave
On Feb 21, 11:12 am, Kunal Patil <[email protected]> wrote:
> 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.
>
> My logic is :
> 1) Sort the given points on the basis of their X-coordinates (NlogN)
> 2) Select first point and Binary Search for negative of its X-
> coordinate (LogN)
> 3) If it returns true we are done else select sencond point and so
> on....(NlogN in worst condition)
>
> Am i Correct ??? Any more solutions ???
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
