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 <[email protected]> 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 <[email protected]> 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 [email protected]. > To unsubscribe from this group, send email to > [email protected]. > 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 [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
