Condition

There is a field of size w * h (1 ≤ w, h ≤ 40000), on which N rooks are placed (0 ≤ N ≤ min (w, h)).

Each rook is given by the coordinate (x, y) (1≤ x ≤ w, 1 ≤ y ≤ h) on the field and beats all the cells that are on the same horizontal or vertical with it. Describe an effective algorithm for finding the largest rectangle in area, the cells of which are not beaten by any of the rooks.

My ideas: I thought, but I didn’t get something logically correct

Closed due to the fact that off-topic by the participants Kromster , Nicolas Chabanovsky ♦ 28 Oct '16 at 11:16 .

  • Most likely, this question does not correspond to the subject of Stack Overflow in Russian, according to the rules described in the certificate .
If the question can be reformulated according to the rules set out in the certificate , edit it .

  • 1 - write your ideas. 2 - the complexity of the correct answer will be O (N log N). - pavel
  • Can the pieces beat each other (i.e., do the fields of different rooks intersect)? - vikttur
  • I do not know, but I think that yes - Max
  • I got two solutions: 1) O (N * log (N)) for computations and O (N) for memory; 2) O (max (w, h)) by computation and O (max (w, h)) by memory. - Roman
  • According to community rules, questions should not be reduced to completing tasks for students. Give an example of your implementation and ask a question describing specific problems. - Nicolas Chabanovsky ♦

1 answer 1

The task is to find the largest rectangle in area. In 2 two-dimensional arrays we will write down the coordinates of the upper left and lower right corner of each square, not under a fight. We start with a [1,1] and b [w, h]. One by one we add the rook to the field and rewrite the squares. Suppose the field is 6x6, the rook is at x = 3, y = 3. Then A [1,1] [1 + x, 1] [1 + x, 1] [1 + x, 1 + x] B [x-1, y-1] [w, y-1] go into masses [x-1, h] [w, h] So, add all the rooks and then find the largest rectangle of 2 pairs of coordinates. Naturally, the coordinates of the previous iterations will need to be deleted from the array, and the coordinates whose area length is 0 will be deleted.

I'm not sure that this is very effective, but in terms of memory requirements and speed for olympiad tasks I have to climb. Or at least give ground for reflection)