On Thu, Oct 14, 2010 at 10:00 PM, Mridul Malpani <malpanimri...@gmail.com>wrote:
> by forming n*n pairs of points. now you have to select any 2 pair such
> that these 2 set have atleast 1 points in common, and their slope must
> be equal.
>
> this will take O(n^4).
> correct me, if i m wrong.
>
I think Dave is correct,
let us consider there are n points,
n slopes are stored in an array like this
(1,1) (1,2) (1,3) (1,4) (1,5) ..... (1,n)
(2,2) (2,3) (2,4) (2,5) ..... (2,n)
(3,3) (3,4) (3,5) ..... (3,n)
(4,4) (4,5) ..... (4,n)
so this will take nlogn time
for n rows
1>
for one row it will take logn time( having n elements)
sort this row again nlogn time.
and then in single traverse you will get all the colinear points
in one row(having one point in common)
nlogn [for sort] * logn [for one row slope calculation] + n
= nlogn [for sort] * logn [for one row slope calculation]
= n(logn )^2
for n rows u will have n* n(logn )^2 = n^2 (logn )^2
correct me if i am wrong
>
> On Oct 14, 7:00 am, Dave <dave_and_da...@juno.com> wrote:
> > @Asquare. Yes, you are wrong. If the slope of the line AB equals the
> > slope of the line AC, then points A, B, and C are collinear. One way
> > to look at it is that because AB and AC have the same slope, they are
> > parallel (if you can call coincident lines parallel), and they both
> > contain point A. Therefore, they are coincident.
> >
> > Dave
> >
> > On Oct 13, 3:04 pm, Asquare <anshika.sp...@gmail.com> wrote:
> >
> > > @Dave -
> >
> > > Although what u have posed is correct to an extent but this will also
> > > include cases where the line joining the points are parallel and not
> > > collinear
> > > So we will have to impose a check for one of the points involved
> > > in every two same slopes to be coincident.
> >
> > > Do correct me if i am wrong..
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Regards,
Rahul Patil
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
