@Sankalp: Whoa! My complaint is that the code you presented in
http://groups.google.com/group/algogeeks/msg/9ab2623efeb73311 requires
the line to go through (0,0). I presented an example where it is
impossible to divide the points with a line through (0,0). You
responded by saying that you would just move the origin to the
lowermost point. I reiterated that that would not do. Now you offer a
proof of some unstated proposition that, to me, seems unrelated to
whether you can always divide a set of points into two equal-sized
subsets by a line through the origin.
Dave
On Jan 26, 7:43 am, sankalp srivastava <richi.sankalp1...@gmail.com>
wrote:
> @dave , There is a proof for it .
>
> Let's say there is a point x0 , y0 .. and I claim that between any two
> points ... x1,y1 and x2,y2 assuming they are non-collinear having a
> line b/w them a line of some slope passes somewhere b/w them .This
> collinearity does not affect our result .
>
> Let's say a point x',y' divides this line into ratio m:n , this is the
> point where this line is intersected by the line from x0 , y0 .. as
> x1 ,y1 and x2,y2 are non-collinear , this point will always exist .
> The slope of this line can be determined from the points x0,y0 and
> x',y' , which is always real .hope this makes sense to u !!
>
> On Jan 26, 7:11 am, Dave <dave_and_da...@juno.com> wrote:
>
>
>
> > @Sankalp: So what is your code? And what is the equation of the line?
> > As I said, you can't always use a line through the origin.
>
> > Dave
>
> > On Jan 25, 5:49 am, sankalp srivastava <richi.sankalp1...@gmail.com>
> > wrote:
>
> > > @dave
> > > In this case , I could just shift my origin to the lowermost point :)
>
> > > On Jan 25, 10:14 am, Dave <dave_and_da...@juno.com> wrote:
>
> > > > @Sankalp: I wanted a point far enough outside the region that a line
> > > > from any point in the region could not contain any other point in the
> > > > region. There are several implications: 1) if the point is to the left
> > > > of the region, it can't have an integer y coordinate between 0 and B.
> > > > That is where the 0.5 comes from. Second, it seemed reasonable, but
> > > > not necessary, to put Y near the middle of the range [0, B]. Then I
> > > > just solved for an X that guaranteed that the slope of the line from
> > > > any point in the region to the point (X, Y) had slope m satisfying -1/
> > > > A < m < 1/A. Then a line through any point (x1,y) could not intersect
> > > > any point (x2,y-1) or (x3,y+1) within the region.
>
> > > > Regarding your algorithm: What does it do with A = B = 5 and points
> > > > {(1,1), (2,2), (3,3), (4,4), (1,4)}. This example shows that you can't
> > > > always use a line through (0,0).
>
> > > > Dave
>
> > > > On Jan 24, 10:15 pm, sankalp srivastava <richi.sankalp1...@gmail.com>
> > > > wrote:
>
> > > > > @
> > > > > 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.-Hidequotedtext-
>
> > > > > > > - Show quoted text -- Hide quoted text -
>
> > > > > - Show quoted text -- Hide quoted text -
>
> > > - Show quoted text -- 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.
