Given $N$ points on a $2D$-plane of type , each coordinate of type $(x,y)$. We need to make a rectangle on this plane in such a way that maximum number of points lie on the boundary of this rectangle.

Note : No two points can have same X coordinate. Area of rectangle drawn can be zero also.

How to find maximum number of points that can be on boundaries of drawn rectangle.

Example : Let there are 5 points. Points are : $(0,2) , (1,3) , (2,4) , (3,1) , (4,1).$

Then here answer is $4.$ As we can have four points only satisfying this criteria.

  • 1
    $\begingroup$ Can the rectangle can be rotated, or do its sides have to parallel to the coordinate axes? $\endgroup$ – bubba Nov 28 '15 at 8:50
  • $\begingroup$ @bubba Good question :) . Sorry i missed it. It need to be parallel to the axis $\endgroup$ – mat7 Nov 28 '15 at 17:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.