@
Dave
How did you come up with this solution?
Also Y=floor(B)/2+.5 , X=-A*(B-Y) or X=-AB +AY or Y=X/A+B . this is
the equation of a line with slope 1/A and an intercept of B on Y
axis .I don't quite get this.!!Please elaborate .
Meanwhile , this is my approach .
The slope of the line wil be between the maximum's of the two points
i.e in the case of (10,0)..(10,10)...It will be between 0 and 90
degrees as all the points lie between them . Now we can just binary
search over this slope checking for the slope values . The slope and
set cardinality is also a monotonic function , so I guess binary
search approach will work , but the time taken will be nlog n . Please
correct me if I'm wrong .
#include<iostream>
struct point
{
int x ;
int y ;
};
using namespace std ;
// the given points
point p[100];
int main()
{
int n;
cin>>n;//number of points
for(int i=0;i<n;i++)
{
cin>>p[i].x>>p[i].y;
}
int high=90;
int low=0;
int mid;
//the line is supposed to start from 0,0
while(low<=high)
{
mid=(high+low)/2;
if(haspoints(mid)<0)
//upper has less points than below
low=mid+1;
else if(haspoints(mid)>0)
//lower has more points than upper
high=mid-1;
else
{//we found our answer
cout<<mid<<endl;
return 0;
}
}
return 0;
}
On Jan 24, 9:30 am, Dave <dave_and_da...@juno.com> wrote:
> Generalizing the problem, let there be n points (x_i, y_i), where x_i
> and y_i are integers with 1 <= x_i <= A and 1 <= y_i <= B. A line
> separating the points into two sets of equal cardinality can be found
> as follows: Let Y = floor(B/2) + 0.5, and let X = -A * (B - Y). Find
> the slopes of the lines from the point (X, Y) to each (x_i, y_i). The
> point (X, Y) is constructed so that each of these slopes will be
> distinct. Find the median M of these slopes. Then the line
>
> y = M(x - X) + Y
>
> will separate the points as desired. It will pass through exactly one
> of the points if n is odd, and will miss all of the points if n is
> even. This is O(n) in time and O(n) in space, where n is the number of
> points.
>
> Dave
>
> On Jan 21, 11:45 pm, Divya Jain <sweetdivya....@gmail.com> wrote:
>
>
>
> > assume the region to be (0,0) , (10,0), (0,10), (10,10)
>
> > On 22 January 2011 08:33, Dave <dave_and_da...@juno.com> wrote:
>
> > > @Divya: The coordinates of the points are between 0 and 1 and are
> > > integers. That can't be right.
>
> > > Dave
>
> > > On Jan 21, 1:46 pm, divya <sweetdivya....@gmail.com> wrote:
> > > > Within a 2D space, there is a batch of points(no duplicate) in the
> > > > region (0,0),(0,1),(1,0),(1,1), try to find a line which can divide
> > > > the region to 2 parts with half points in each .the input will be an
> > > > array of points and the length of the array.
> > > > struct point{
> > > > int x;
> > > > int y;};
>
> > > > input : struct point * points, int length
>
> > > --
> > > You received this message because you are subscribed to the Google Groups
> > > "Algorithm Geeks" group.
> > > To post to this group, send email to algogeeks@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com<algogeeks%2Bunsubscribe@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 algogeeks@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.
