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$ ($1$ ≤ $n$, $m$ ≤ $100$, $1$ ≤ $k$ ≤ $1000$) — the height, the width of the fixed rectangle and the number of rectangles to be placed.↵
↵
The next $k$ lines have two integers $x_{i}$ and $y_{i}$ ($1$ ≤ $x_{i}$ ≤ $n$, $1$ ≤ $y_{i}$ ≤ $m$) — 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 $x_{j}$ and $y_{j}$ 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](/predownloaded/07/9c/079c3338d54642a40e33df66d30378d1e2197bfa.png)↵
↵
[Illustration application](https://drive.google.com/drive/folders/0B0aBLbDIvtoDbDFMMEZGMEtmdEk)↵
↵
**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.↵
↵
#### 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$ ($1$ ≤ $n$, $m$ ≤ $100$, $1$ ≤ $k$ ≤ $1000$) — the height, the width of the fixed rectangle and the number of rectangles to be placed.↵
↵
The next $k$ lines have two integers $x_{i}$ and $y_{i}$ ($1$ ≤ $x_{i}$ ≤ $n$, $1$ ≤ $y_{i}$ ≤ $m$) — 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 $x_{j}$ and $y_{j}$ 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](/predownloaded/07/9c/079c3338d54642a40e33df66d30378d1e2197bfa.png)↵
↵
[Illustration application](https://drive.google.com/drive/folders/0B0aBLbDIvtoDbDFMMEZGMEtmdEk)↵
↵
**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.↵
