@Sudheer: We don't need to do any extra work to eliminate it. It is a
smaller set than the previous max found, so we don't have to consider
it further. The problem says "the maximum set," and doesn't specify
what to do in the case of ties. Since apparently one answer is
expected, I assume that it means "a maximal set," so you can ignore
any set that is not larger than the current max.
Dave
On Oct 13, 6:41 am, sudheer babu <sudheervaddep...@gmail.com> wrote:
> suppose after caliculating slopes for ist point we formed set points(n=9)
> whose slopes are eequal are
> {1,2,3,4},{1,5,6,7,9},{1,}.
> now for second point we will definitely get 1 set{1,2,3,4}and some other and
> we have to eliminate this set
> it takes some more time
>
>
>
> On Wed, Oct 13, 2010 at 5:52 PM, Dave <dave_and_da...@juno.com> wrote:
> > @Mridul: For each point i, find the slope to every other point j and
> > look for duplicates. Duplicates can be found by sorting the slopes and
> > comparing adjacent values. Point i is collinear with the points in
> > each set of duplicates. Keep track of the maximal set as you go.
>
> > For each i, you have n-1 slopes to calculate and sort and compare.
> > Therefore, using a log n sort, the complexity of the algorithm is
> > O(n^2 log n).
>
> > Dave
>
> > On Oct 13, 4:52 am, Mridul Malpani <malpanimri...@gmail.com> wrote:
> > > There are n points in 2d space.we have their (x,y) co-ordinates. you
> > > have to find the maximum set of points that are colinear?
> > > I have used brute force, time =O(n^4). he wants a solution in O(n^3 or
> > > n^2).
>
> > --
> > 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.- Hide quoted text -
>
> - Show quoted text -
--
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.
