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, In English,

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.

 
 
 
 
  • Vote: I like it
  • +10
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you provide me with a code for that ? a google link or so.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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, # |
  Vote: I like it 0 Vote: I do not like it

Do the points and the square's co-ordinates have to be integers?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I have the problem link?

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

" kindly do not downvote this post". Weep bro weep..... Ro do tum ro do:p

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.