#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y;
bool operator<(const Point p) const { return x < p.x || (x == p.x && y < p.y); }
int dist(const Point p) const { return abs(p.x - x) + abs(p.y - y); }
bool operator==(const Point p) const { return x == p.x && y == p.y; }
};
ostream& operator<<(ostream& os, const Point p) {
return os << "(" << p.x << ", " << p.y << ")";
}
string polygon_to_str(const vector<Point>& polygon) {
stringstream ss;
ss << fixed << setprecision(6);
ss << "polygon(";
for (size_t i = 0; i < polygon.size(); i++) {
if (i > 0) ss << ", ";
ss << polygon[i];
}
ss << ")";
return ss.str();
}
struct Segment {
Point p, q;
string to_desmos() const {
stringstream ss;
ss << fixed << setprecision(6) << "\\left(\\left(1-t\\right)\\cdot" << p.x + 0.5
<< "+t\\cdot" << q.x + 0.5 << ",\\left(1-t\\right)\\cdot" << p.y + 0.5
<< "+t\\cdot" << q.y + 0.5 << "\\right)";
return ss.str();
}
};
int main() {
int n;
Point dest;
while (cin >> dest.x >> dest.y >> n) {
cerr << endl << "---------------------------------------------" << endl << endl;
vector<tuple<int, int, int, int>> events;
for (int i = 0; i < n; i++) {
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
if (x1 > x2) swap(x1, x2);
if (y1 > y2) swap(y1, y2);
// if (dest.x < x1) continue;
// TODO: Maybe I can use each y independently on each event (no need to have both in
// one item). I think I need to remove in the range, so I can't do that!!!
events.emplace_back(x1 - 1, 1, y1 - 1, y2 + 1);
events.emplace_back(x2 + 1, 0, y1 - 1, y2 + 1);
vector<Point> poly;
poly.emplace_back(x1, y1);
poly.emplace_back(x2 + 1, y1);
poly.emplace_back(x2 + 1, y2 + 1);
poly.emplace_back(x1, y2 + 1);
cerr << polygon_to_str(poly) << endl;
}
// TODO: what should the type be in this event????
events.emplace_back(dest.x, -1, dest.y, dest.y);
sort(events.begin(), events.end());
map<int, Point> m;
map<Point, Point> prev_point;
const int inf = 1e7;
m[0] = {0, 0};
// TODO: Maybe this will overflow in some cases.
// TODO: This data is weird lmao
m[INT_MIN] = {0, -inf};
m[INT_MAX] = {0, inf};
const auto update = [&](const int x, const int y) {
const auto it0 = m.lower_bound(y);
assert(it0 != m.end());
assert(it0 != m.begin());
const auto it1 = it0->first == y ? it0 : prev(it0);
const Point p{x, y};
// cerr << p << endl;
if (prev_point.count(p)) return;
if (p.dist(it0->second) < p.dist(it1->second)) {
// use it0
prev_point[p] = it0->second;
m[p.y] = p;
} else {
// use it1
prev_point[p] = it1->second;
m[p.y] = p;
}
// cerr << prev_point[p] << " ----> " << p << endl;
};
for (const auto& [x, type, y1, y2] : events) {
// cerr << format("x: {}, type: {}, y = [{}, {}]", x, type, y1, y2) << endl;
// cerr << "type: " << type << endl;
// TODO: I'm not using the `type` lol
if (type == -1) {
update(x, y1);
} else {
update(x, y1);
update(x, y2);
}
// TODO: I think I have to remove the items between y1 and y2???????
while (true) {
const auto it = m.lower_bound(y1 + 1);
// TODO: This line fixed it?? but verify what I did (the -1 specifically)
if (y2 - 1 <= it->first) break;
m.erase(it);
}
// cerr << "curr map content:" << endl;
// for (const auto& [y, p] : m) {
// cerr << " " << y << " : " << p << endl;
// }
}
vector<Point> path;
Point curr = dest;
while (!(curr.x == 0 && curr.y == 0)) {
path.emplace_back(curr);
if (!prev_point.count(curr)) {
cerr << "not found!!!!!!!!!!!!!!! prev of : " << curr << endl;
assert(false);
// break;
}
// assert(prev_point.count(curr));
if (curr == prev_point[curr]) {
cerr << "equal!!!!!!!!!!!!!! " << curr << endl;
assert(false);
// break;
}
curr = prev_point[curr];
}
path.emplace_back(curr);
reverse(path.begin(), path.end());
vector<Point> fixed_path;
for (size_t i = 0; i < path.size() - 1; i++) {
fixed_path.emplace_back(path[i]);
if (path[i].x < path[i + 1].x) {
fixed_path.emplace_back(path[i + 1].x, path[i].y);
}
}
fixed_path.emplace_back(path.back());
int total_len = 0;
for (size_t i = 0; i < path.size() - 1; i++) {
total_len += path[i].dist(path[i + 1]);
}
for (size_t i = 0; i < fixed_path.size() - 1; i++) {
const Point p = fixed_path[i];
const Point q = fixed_path[i + 1];
cerr << Segment{p, q}.to_desmos() << endl;
}
cout << total_len << endl;
}
}
