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
-~----------~----~----~----~------~----~------~--~---
