GATE CSE 2000 | Question: 14

Question

Consider the line $y=\frac{n}{m}x$, where $n$ and $m$ are positive integers.

1. If mq - np < 0, then is the point (p,q) above the line, below the line, or on the line?
2. Complete the following function, that returns true if the line segment with endpoints (p,q) and (r,s) intersects the line $y=\frac{n}{m}x$, by writing the line number and the content of each box in your answer book.

  1: function clash (m, n, p, q, r, s: integer): Boolean;
  2: begin
  3: clash = false;
  4: if(m*q - n*p)⊏⊐ 0 then clash:= true;
  5: if(m*s - n*r)⊏⊐ 0 then clash:= true;
  6: if(m*q - n*p)⊏⊐ 0 and (m*s - n*r)⊏⊐ 0 then clash:= true;
  7: if(m*q - n*p)⊏⊐ 0 and (m*s - n*r)⊏⊐ 0 then clash:= true;
  8: end;

Comments

@Arjun sir Can someone provide solution for this? Thanks

Answer 1

(a) Above/Below Test

 

For the line \( y = \tfrac{n}{m}x \), define  

F(x,y) = m y - n x .

 

- If \(F(p,q) < 0\): the point \((p,q)\) is below the line.  

- If \(F(p,q) > 0\): the point \((p,q)\) is above the line.  

- If \(F(p,q) = 0\): the point \((p,q)\) lies on the line.  

 

So, if \(m q - n p < 0\), then \((p,q)\) is below the line.

 

(b) Completing the Function

 

Let  

A = F(p,q) = m q - n p, 

B = F(r,s) = m s - n r .

 

A line segment with endpoints \((p,q)\) and \((r,s)\) intersects the line if:

 

1. At least one endpoint lies on the line (\(A = 0\) or \(B = 0\)), OR  

2. The endpoints are on opposite sides (\(A > 0, B < 0\) or \(A < 0, B > 0\)).

 

Final Function

1: function clash (m, n, p, q, r, s: integer): Boolean;

2: begin

3: clash := false;

4: if (m*q - n*p) = 0 then clash := true; // P lies on the line

5: if (m*s - n*r) = 0 then clash := true; // R lies on the line

6: if (m*q - n*p) > 0 and (m*s - n*r) < 0 then clash := true; // Opposite sides

7: if (m*q - n*p) < 0 and (m*s - n*r) > 0 then clash := true; // Opposite sides

8: end;