Блог пользователя thienlongtpct

Автор thienlongtpct, история, 7 лет назад, По-английски

UPD 1: Add the application to automatic draw the rectangle.

Overview

This problem is a varient of the classic problem, "Packing rectangles with the smallest area rectangle.". This is also an optimization with you may not find the most optimal solution but the more rectangles you can place, the more score you get.

In this problem, given the size of the main rectangle and the size of others rectangles, find the maximum number of rectangle could be place in the main rectangle without overlapping the other rectangle ( note: these rectangles must be inside the main rectangle — but it can be touch in the borders of the main rectangle).

Input

The first line contains three integers n, m and k (1n, m100, 1k1000) — the height, the width of the fixed rectangle and the number of rectangles to be placed.

The next k lines have two integers xi and yi (1xin, 1yim) — the height and the width of the rectangle, remember that we can't rotate these rectangles.

Output

The first line of the ouput print k.

The next k line print two number xj and yj is the top — left point where the rectangle j placed. In case we don't place this rectangle, print "0 0" (without quotes).

Sample input

8 7 10
4 5
4 2
2 3
1 1
1 1
1 2
1 5
5 1
6 1
2 1

Sample output

10
1 1
5 1
5 3
1 6
7 3
7 4
8 3
1 7
2 6
6 7

Illustration

Picture for sample test case

Illustration application

Using the application

To use the application, you run your code to make a new ".exe" file (it must be in same folder with the input test). After that, upload the test input by clicking the button "Load input file...". Finally, click the button "Run external solution ..." and chose your ".exe" file.

P/s: Hope you to help with problem in case we want to maximize the area be covered. I just think of the brute force solution and some of the trival greedy approachs.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Does the test case always have atleast one way to place all the rectangles in the main rectangle ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    No, just atleast one rectangle (because all of the height and width of all others rectangles is smaller or equal the main rectangle) to be placed but we not sure that all the rectangle can be place or not.

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Could you give me more test case ?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Here are some testcases that I use. To make it easy, all of the test case have the most optimal solution is all the rectangles can be place.

    Test case

    Brute force code

    Plese note that some of the test case is too big that my code couldn't deal with.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by thienlongtpct (previous revision, new revision, compare).

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

You can using 2D BIT to decrease the operation "inBounnd", ""check", "uncheck". Howerver, this still too slow for your constant.