Luckwet's blog

By Luckwet, history, 14 months ago, In English

C. DIY (ICPC2024-2025)

Let's say we can choose 4 points to make a rectangle. Let the numbers defining the coordinates be arranged in ascending order: a, b, c, d.

Then I have a question. Is there any INTUITIVE proof that it is advantageous to take exactly

xmin = a

ymin = b

xmax = c

ymax = d ?

And not, for example, as I thought at the very beginning

xmin = a

ymin = b

xmax = d

ymax = c.

I have already done the MATHEMATICAL proof, but now I need the INTUITIVE proof.

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

| Write comment?
»
14 months ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

In both cases you have $$$(c - a) + (d - b) = \Delta x + \Delta y = (d - a) + (c - b)$$$. So the rectangle's perimeter is fixed, and you want its area to be as big as possible. To achieve that, it should be as close to square as possible.

»
14 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

It's so funny to watch stupid kids come to this post, downvote my post, downvote the comment of the person who helped me, downvote my reply to that person, and then run away

»
14 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

i thought it like this the side should be parallel to each other so i should have 2 points which are there twice in the array for ex- 0,1 and 0,2 make one parallel side for each axis and greedily choose the 2 least elements and 2 max elements to get the maximum area.