Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### gregr's blog

By gregr, history, 5 weeks ago, ,

All , I have a question for you . We are given a set of points in 2-D plane . we need to form a square centered at origin such that it has max perimeter and does not encloses any of those points . Can you answer this , or can you atleast refer me resources from where can i study this. your reply is greatly appreciated. kindly do not downvote this post, you can get answer if someone replies.

• +10

 » 5 weeks ago, # |   0 One possible solution is to binary search over the angle (rotate the square). Let $p$ be the nearest point to the origin. Let $\vec{p}$ be the position vector $p$. Let one angle be the angle the square points when the side is perpendicular to $\vec{p}$ and is touching $p$. The other angle is the angle the corner makes when the corner touches $p$. For an arbitrary angle between these two, the side length changes such that a side touches $p$.
•  » » 5 weeks ago, # ^ |   0 can you provide me with a code for that ? a google link or so.
•  » » » 5 weeks ago, # ^ |   0 The code will be a little messy. Draw two squares, one with the corner touching $p$ (smallest square), and the other with the side touching $p$ (largest square possible). Now imagine rotating the smaller square to form the larger one while touching $p$. One of these intermediate squares is the most optimal square.
•  » » » » 5 weeks ago, # ^ |   0 So, the side touching p square will be the largest if it touches the middle point of any side. And as we don't what the middle point can be, we need to Binary Search right?
•  » » » » » 5 weeks ago, # ^ |   0 In essence, yes. Point $p$ can be anywhere from the midpoint of the side to the corner. Binary search over the position of $p$.
 » 5 weeks ago, # |   0 Do the points and the square's co-ordinates have to be integers?
•  » » 5 weeks ago, # ^ |   0 no
 » 5 weeks ago, # |   0 Can I have the problem link?
 » 4 weeks ago, # |   +3 " kindly do not downvote this post". Weep bro weep..... Ro do tum ro do:p
 » 4 weeks ago, # |   0 You can represent your square boundaries by 4 points, ymin, ymax, xmin and xmax. Let's try to bound them. For every point just relax these 4 points. Side of square should be absMin(ymix, ymax, xmin, xmax). absMin(int...) is minimum over absolute values.