pardon 1 small mistake
instead of
if(i == 0 || i == n)
return (lower, upper);
it should be
if(i == lower || i == upper)
return (lower, upper);
On Sat, Aug 27, 2011 at 8:31 PM, Piyush Grover <piyush4u.iit...@gmail.com>wrote:
> satisfy the point on lines, for point(x,y) to lie in between the two, the
> f(x,y) value would have different sign.
> This can be done using the binary search approach. Here is the pseudo code:
> f(x,y) = Ax + By - C
> (x0, y0)
> initial Call: SearchLines(f, n/2, 0, n);
> SearchLines(f, i, lower, upper){
>
> if(i == 0 || i == n)
> return (lower, upper);
> if (f [i] (x0, y0) < 0){
> lower = i;
> mid = (i + upper)/2;
> SearchLines(f, mid, lower, upper);
> }else if(f [i] (x0, y0) > 0){
> upper = i;
> mid = (i+lower)/2;
> SearchLines(f, mid, lower, upper);
>
> }else{
> if(f [i+1] (x0,y0) < abs(f[i-1] (x0, y0)) )
> return(i, i+1)
> else return(i-1, i);
>
>
> }
>
> }
>
> On Sat, Aug 27, 2011 at 5:59 PM, Piyush Grover
> <piyush4u.iit...@gmail.com>wrote:
>
>> I don't understand your point if y[i] < y[i+1]
>> how come the slope is positive?
>> It's just that the i'th line will lie under line i+1th line.
>>
>>
>>
>> On Sat, Aug 27, 2011 at 5:11 PM, monish001 <monish.gup...@gmail.com>wrote:
>>
>>> If I correctly understood the question, It says:
>>> 1. 0<= x[i] <=1 for all i and for all x of line i.
>>> 2. y[i]<y[i+1] means lines have positive slope
>>>
>>> If line i is f(x,y): A[i]x + B[i]y -C[i], Use the following concept:
>>> 1. Find 1 line closest to the given point such that f(x,y) is of same
>>> sign for both (0,0) and given point.
>>> 2. Find other line closest to the given point such that f(x,y) is of
>>> opposite signs for both (0,0) and given point.
>>>
>>> To check which line is closest, use the formula which finds the
>>> (perpendicular) distance between the line and the point.
>>> I am not sure about the correctness of the following formula:
>>> If distance of x,y from ax+by=c is d.
>>>
>>> d = sqrt(2)*( (a*a + b*b - c) / (a-b) )
>>>
>>>
>>> -Monish
>>> On Aug 26, 6:19 am, Ankur Garg <ankurga...@gmail.com> wrote:
>>> > You are given n no. of lines in form of Ax + By = C, basically you are
>>> given
>>> > A[i], b[i] and C[i] for line "i".
>>> > Lines are given in a way such that 0 <= x[i] <= 1 and y[i] < y[i+1] for
>>> same
>>> > X.
>>> > Also, one point (x,y) is given too. Find out the two closest lines to
>>> the
>>> > point such that the point is between them.
>>> > Given: n - no. of lines
>>> > a[i] b[i] c[i] - i th line.
>>> > X Y - Point
>>> > Output
>>> > A[i] B[i] C[i]
>>> > A[j] B[j] C[j]
>>> > such that the point X,Y is between them.
>>>
>>> --
>>> 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.
>>>
>>>
>>
>
--
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.
