#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int maxn = 310, maxc = 42;
int n, r, c;
int x[maxn], y[maxn];
struct node
{
node *lc, *rc;
int mx, cnt, lazy;
node()
{
mx = 0;
cnt = 0;
lazy = 0;
lc = rc = NULL;
}
};
void make_kids(node *root, int left, int right)
{
int mid = (left + right) / 2;
if (root -> lc == NULL)
{
root -> lc = new node();
root -> lc -> cnt = mid - left + 1;
}
if (root -> rc == NULL)
{
root -> rc = new node();
root -> rc -> cnt = right - mid;
}
}
void push_lazy(node *root)
{
root -> mx += root -> lazy;
if (root -> lc != NULL)
{
root -> lc -> lazy += root -> lazy;
root -> rc -> lazy += root -> lazy;
}
root -> lazy = 0;
}
void unite(node *root)
{
root -> mx = min(root -> lc -> mx, root -> rc -> mx);
root -> cnt = 0;
if (root -> lc -> mx == root -> mx)
root -> cnt += root -> lc -> cnt;
if (root -> rc -> mx == root -> mx)
root -> cnt += root -> rc -> cnt;
}
void update_range(node *root, int left, int right, int qleft, int qright, int val)
{
if (left != right)
make_kids(root, left, right);
push_lazy(root);
if (left > qright || right < qleft)
return;
if (left >= qleft && right <= qright)
{
root -> lazy += val;
push_lazy(root);
return;
}
int mid = (left + right) / 2;
update_range(root -> lc, left, mid, qleft, qright, val);
update_range(root -> rc, mid + 1, right, qleft, qright, val);
unite(root);
///cout << "return " << left << " " << right << " " << root -> mx << " " << root -> cnt << endl;
}
struct line
{
int y, x_up, x_dw;
int t;
line(int _y = 0, int _x_dw = 0, int _x_up = 0, int _t = 0)
{
y = _y;
x_up = _x_up;
x_dw = _x_dw;
t = _t;
}
};
struct event
{
int t;
line l;
event(int _t = 0, line _l = line())
{
t = _t;
l = _l;
}
};
set < int > set_x, set_y;
bool cmp(event e1, event e2)
{
///if (e1.l.y == e2.l2.y)
///return e1.t < e2.t;
return e1.l.y < e2.l.y;
}
bool check(int h, int w)
{
for (int rel : set_x)
{
node *root = new node();
root -> cnt = r;
unordered_map < ll, ll > prec;
vector < event > events;
for (int i = 1; i <= n; i ++)
{
event op, en;
op.t = en.t = 1;
op.l = line(y[i], x[i], x[i] + h - 1, 1);
en.l = line(y[i] + w, x[i], x[i] + h - 1, -1);
events.push_back(op);
events.push_back(en);
}
for (int y : set_y)
{
events.push_back(event(2, line(y, 0, 0, 0)));
events.push_back(event(2, line(y + c, 0, 0, 0)));
}
sort(events.begin(), events.end(), cmp);
ll area = 0;
ll last = 0;
//cout << "range " << rel << " " << rel + r - 1 << endl;
for (event cur : events)
{
//cout << "event " << cur.l.y << " area " << area << endl;
//if (cur.t == 1)
// cout << "line " << cur.l.x_dw << " " << cur.l.x_up << " " << cur.l.t << endl;
ll act = r;
if (root -> mx == 0)
act -= root -> cnt;
//cout << "rem " << root -> cnt << endl;
area += act * (ll)(cur.l.y - last);
last = cur.l.y;
if (cur.t == 2)
{
prec[cur.l.y] = area;
}
else
{
int lx = max(rel, cur.l.x_dw);
int rx = min(rel + r - 1, cur.l.x_up);
update_range(root, rel, rel + r - 1, lx, rx, cur.l.t);
}
}
/*for (int y : set_y)
{
cout << y << " : " << prec[y] << endl;
}*/
for (int y : set_y)
{
ll ar = prec[y + c] - prec[y];
if (ar == (ll)(r) * (ll)(c))
return true;
}
}
return false;
}
void solve()
{
cin >> r >> c;
cin >> n;
for (int i = 1; i <= n; i ++)
cin >> x[i] >> y[i];
for (int i = 1; i <= n; i ++)
{
set_x.insert(x[i]);
set_y.insert(y[i]);
}
//cout << check(3, 2) << endl;
//exit(0);
int ans = r + c - 2;
for (int h = 1; h <= r * 2; h ++)
{
int lf = 1, rf = c * 2;
while(lf <= rf)
{
int w = (lf + rf) / 2;
if (check(h, w))
rf = w - 1;
else
lf = w + 1;
}
ans = min(ans, lf + h - 2);
}
cout << ans << endl;
}
int main()
{
solve();
return 0;
}
/**
40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
180 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
180 ms |
262144 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
