Hi Malay,
Thanks for the solution.
Thanks,
Raghavendra
On Tue, Jun 3, 2008 at 5:02 PM, Malay Bag <[EMAIL PROTECTED]> wrote:
> Please consider this method...
>
> with respect to first point sort (in place) other n-1 ponits comparing the
> angles (between the horizontal line passing through 1st point and the line
> passing through 1st point and current point)... (nlogn) (merge sort may be
> used)
> checke for 3 collinear points (nlogn)
>
> now for i=n-1 to 3
> {
> swap 1st point and (i+1)th point; (we have already taken care of 1st point
> and i+2, i+3, ..., n th points)
> with respect to the new 1st point, sort (in place) other i-1 ponits
> comparing the angles (between the horizontal line passing through 1st point
> and the line passing through 1st point and current point)... (ilogi)
> checke for 3 collinear points (ilogi)
> }
>
> Thanks
> Malay
>
>
> On Mon, Jun 2, 2008 at 12:34 PM, Raghavendra Sharma <
> [EMAIL PROTECTED]> wrote:
>
>> Hi Guys,
>>
>> Can anyone please give me a solution for this??
>>
>> On a plane if there are n points. How to find out if there are three (3)
>> points which are collinear in O(N**2log n) time. I got a solution which uses
>> extra space. But i need a solution which doesn't use any extra space.
>>
>>
>> Thanks,
>> Raghavendra
>>
>> On Fri, May 30, 2008 at 9:26 AM, Raghavendra Sharma <
>> [EMAIL PROTECTED]> wrote:
>>
>>> Hi,
>>>
>>>
>>> On a plane if there are n points. How to find out if there are three (3)
>>> points which are collinear in O(N**2log n) time. I got a solution which uses
>>> extra space. But i need a solution which doesn't use any extra space.
>>>
>>>
>>> Thanks,
>>> Raghavendra
>>>
>>
>>
>>
>>
>
>
> --
> " I would love to change the world, but they won't give me the source code.
> "
> >
>
--~--~---------~--~----~------------~-------~--~----~
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
-~----------~----~----~----~------~----~------~--~---
