@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 - -- 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.