### 2011 Canadian Computing Competition, Stage 2

## Day 2, Problem 3: Biggest (Zero Carbon) Footprint

Having just recently won the lottery, you decide to build a summer resort nestled deep in a forest. However, being a very eco-friendly person, you decide not to cut down any of the trees that grow in the forest. Given a map of the forest and the positions of its trees, determine the area of the largest rectangular plot you can buy that does not contain any of the trees. (Note that your plot must have edges which are parallel to the x and y axes.)

### Input Format

The first line contains `n`, `m`, and `t`
(0 ≤ `n`, `m` ≤ 10000,
0 ≤ `t` ≤ 10000), representing the
dimensions of the given map of the forest and the number of trees indicated on
the map respectively. The next `t` lines each contain two integers
`x` and `y`
(0 ≤ `x` ≤ `n`,
0 ≤ `y` ≤ `m`) describing the
location of each tree (where (0,0) is the bottom leftmost point on the map and
(`n`,`m`) is the top rightmost point on the map).

Note: for 20% of the marks for this question, you may assume that
`t` ≤ 100, and for 45% of the marks for this question,
`t` ≤ 400.

### Output Format

Output the area of the largest rectangle that does not contain any of the given trees.

### Sample Input

5 5 2 1 1 3 3

### Sample Output

12

All Submissions

Best Solutions

**Point Value:** 25 (partial)

**Time Limit:** 5.00s

**Memory Limit:** 256M

**Added:** Jun 06, 2011

**Languages Allowed:**

C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

## Comments (Search)

xiaowuc1on Aug 07, 2014 - 7:53:08 am UTC Formal definition of "inside the rectangle"thorthugnastyon Dec 27, 2014 - 10:40:37 pm UTC Re: Formal definition of "inside the rectangle"thorthugnastyon Jan 04, 2015 - 4:18:20 am UTC Re: Formal definition of "inside the rectangle"Danielon Jun 06, 2011 - 2:20:02 am UTC Higher point value?