Partition into Rectangles
Limits: 2 sec., 256 MiB
This statement was translated automatically from Ukrainian.
Marichka has points \((x, y)\) on the plane for all integers \(x, y\) such that \(0 \le x < n, 0 \le y < m\). She connected some \(k\) pairs of points with each other.
Zenyk wants to partition the entire region into rectangles such that connected points belong to different rectangles. To do this, he chooses positive integers \(a\) and \(b\) such that \(a \le n, b \le m\), and draws a horizontal line every \(a\) points and a vertical line every \(b\) points. Thus, the region will be divided into \(\left \lceil{\frac{n}{a}}\right \rceil \cdot \left \lceil{\frac{m}{b}}\right \rceil\) (division rounded up) rectangles. More formally, the point \((x, y)\) will belong to the rectangle with coordinates \(\left(\left \lfloor{\frac{x}{a}}\right \rfloor, \left \lfloor{\frac{y}{b}}\right \rfloor \right)\) (integer division).
Marichka told Zenyk that she does not like small rectangles. Therefore, Zenyk must maximize the product \(a \cdot b\).
Help Zenyk, write a program for him.
Input
The first line contains three integers \(n\), \(m\), \(k\).
The next \(k\) lines contain four integers \(x_1, y_1, x_2, y_2\). This means that the point \((x_1, y_1)\) is connected to the point \((x_2, y_2)\).
Output
In a single line, print an integer — the maximum possible product \(a \cdot b\).
Constraints
\(1 \le n, m \le 200\),
\(1 \le k \le 10^5\),
\(0 \le x < n, 0 \le y < m\) for all points encountered in the input,
\((x_1, y_1) \ne (x_2, y_2)\) for all pairs of points that are connected to each other,
each pair of connected points appears only once,
for 15 tests, additional constraints \(n, m \le 100, k \le 10^3\) hold.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 4 7 7 0 6 1 2 1 3 2 2 3 4 2 0 3 2 1 1 0 1 0 4 0 5 3 5 3 6 1 6 | 9 |
Notes
In the example, it is optimal to choose \(a=3,b=3\).
Submit a solution
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|
Partition into Rectangles - Editorial
A solution in \(O(nmk)\): go over all possible \(a\) and \(b\) and check whether the connected points belong to different rectangles.
A solution in \(O(n(m^2+k))\): go over \(a\). If for some connected points \((x_1, y_1), (x_2, y_2)\) we have \(\left \lfloor{\frac{x_1}{a}}\right \rfloor \ne \left \lfloor{\frac{x_2}{a}}\right \rfloor\), these points are in different rectangles. Now we consider only the pairs of points for which this does not hold. We need to satisfy the condition \(\left \lfloor{\frac{y_1}{b}}\right \rfloor \ne \left \lfloor{\frac{y_2}{b}}\right \rfloor\).
Now we have a one-dimensional problem. To solve it, we introduce an array \(d\). The value \(d[i]\) is the smallest \(y\) coordinate not less than \(i\) among all points connected to some point with \(y\) coordinate \(i\). In other words, it is the coordinate of the nearest point above connected to a point with \(y\) coordinate \(i\). After computing this array, we can go over \(b\) and check whether the condition \(\left \lfloor{\frac{i}{b}}\right \rfloor \ne \left \lfloor{\frac{d[i]}{b}}\right \rfloor\) holds for all \(i\).
| Element Type | Created | Who | Problem | Compiler | Result | Time (sec.) | Memory (MiB) | # | Actions |
|---|