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.
