#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using Point = pair<int, int>;
map<Point, vector<pair<Point, bool>>> adj;
map<Point, int> best;
map<Point, Point> prevv;
map<Point, bool> prevDir;
int dist(Point& a, Point& b)
{
return abs(a.first - b.first) + abs(a.second - b.second);
}
void add(Point& a, Point& b, bool dir)
{
if (a != b) adj[a].push_back({b, dir});
}
int main()
{
cin.tie(NULL) -> sync_with_stdio(false);
int destX, destY, N;
cin >> destX >> destY >> N;
vector<array<int, 4>> 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 (x1 - 1 >= destX)
continue;
events.push_back({x1 - 1, y1 - 1, y2 + 1, 0});
events.push_back({x2 + 1, y1 - 1, y2 + 1, 1});
best[{x1 - 1, y1 - 1}] = 1E9;
best[{x1 - 1, y2 + 1}] = 1E9;
best[{x2 + 1, y1 - 1}] = 1E9;
best[{x2 + 1, y2 + 1}] = 1E9;
}
best[{destX, destY}] = 1E9;
events.push_back({0, 0, 0, 1});
events.push_back({destX, destY, destY, 0});
sort(events.begin(), events.end(), [](auto& a, auto& b)
{
if (a[0] == b[0])
{
if (a[3] ^ b[3]) // one of them end
return a[3] == 1;
return a[1] < b[1];
}
else
return a[0] < b[0];
});
// y, x
map<int, int> active;
for (auto& [x, y1, y2, _] : events)
{
auto it = active.lower_bound(y1);
Point lo = {x, y1}, hi = {x, y2};
while (it != active.end() && it -> first <= y2)
{
Point p = {it -> second, it -> first};
add(p, lo, true);
add(p, hi, true);
it = active.erase(it);
}
// connect points outside of segment
it = active.upper_bound(y2);
if (it != active.end())
{
Point p = {it -> second, it -> first};
add(p, hi, false);
}
it = active.lower_bound(y1);
if (it != active.begin())
{
--it;
Point p = {it -> second, it -> first};
add(p, lo, false);
}
active[y1] = x;
active[y2] = x;
}
using T = pair<int, Point>;
priority_queue<T, vector<T>, greater<T>> q;
q.push({0, {0, 0}});
best[{0, 0}] = 0;
while (!q.empty())
{
auto [d, point] = q.top();
q.pop();
for (auto& [u, dir] : adj[point])
{
if (d + dist(point, u) < best[u])
q.push({best[u] = d + dist(point, u), u}), prevv[u] = point, prevDir[u] = dir;
}
}
vector<Point> path;
Point stop = {-1, -1};
prevv[{0, 0}] = stop;
Point p = {destX, destY};
while (prevv[p] != stop)
{
path.push_back(p);
p = prevv[p];
}
path.push_back({0, 0});
reverse(path.begin(), path.end());
vector<Point> ans;
for (int i = 1; i < path.size(); ++i)
{
int dx = path[i].first - path[i - 1].first;
int dy = path[i].second - path[i - 1].second;
if (ans.empty())
{
if (prevDir[path[i]])
{
if (dx) ans.push_back({dx, 0});
if (dy) ans.push_back({0, dy});
}
else
{
if (dy) ans.push_back({0, dy});
if (dx) ans.push_back({dx, 0});
}
continue;
}
if (prevDir[path[i]]) // x first
{
if (ans.back().first == 0)
{
if (dx)
{
ans.push_back({dx, 0});
if (dy)
ans.push_back({0, dy});
}
else
ans.back().second += dy;
}
else
{
ans.back().first += dx;
if (dy)
ans.push_back({0, dy});
}
}
else
{
if (ans.back().first == 0)
{
ans.back().second += dy;
if (dx)
ans.push_back({dx, 0});
}
else
{
if (dy)
{
ans.push_back({0, dy});
if (dx)
ans.push_back({dx, 0});
}
else
ans.back().first += dx;
}
}
}
cout << best[{destX, destY}] << endl;
cout << ans.size() << endl;
for (auto [dx, dy] : ans)
cout << dx << ' ' << dy << '\n';
return 0;
} /*****************************=
-+**********************************=
:-*****************************************+:
..:*************+=+*******************************=.
..-==*****************+=-+*****************************+.
..-=***********************+--+****************************=
:+**************#*#**********+--+***************************- .=--=.
.+*********************#*********+--****************************++++----:
-+***********************##*********--+********************************+--=.
=****=**********************#*********+-=***************************#*****+--=
.=****+***********************************-=*********************#*****##*****=-=.
:=*****=************************************=-*****************#******#####*****=-=.
.=**+***=**************************#**********==***********##*******#**######*****+-=.
+***=***+***************************#**********-+*****####********#*****#####******+-=:
=+**=****+****************#**********************-*####*********##***#*#######*******+-=.
.=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=.
=**#++****=***#******#******#***********#**********=*******####****##**#########********=-=
.=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-==
-*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*.
=*###+######+############################################=..+=-+.########%##%##%##########*-+*
+###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#.
.+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+
.-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+##
.=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*##
.+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%= #%%############=###-
.+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+ #%%###########*=###+
:=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####-
.#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+ %%######%#####=*####.
#* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%- %%######%#####=#####.
-# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%# #%######%####*=###%#
*. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%* #%######%####+*###%#
*.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%# +%######%####=####%#.
=.=###%%%%%:.............:............#*%%####*#*=====%@%%% :%#####%%####+######:
.=%##%%%%%*.............:............#*%%####+#+======%#%* .:-=%%%%%%%%###+#####+#-
.%%##%%%-*-..............::::.......#+%%####+#=====-...#: :*%%%%%%%%%%%%%%%%###*#####=#=
.####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+
*-#%#%%- -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#*
=*.%%%%= .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*#
#..%%%#. -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*#
+- :%%%#+ =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:.
.#. =%% .*= -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+.
.* *%- .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#.
.=. ## ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%:
..=*- .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-.
#@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:.
*@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=:
:@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:
.%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%:
.-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@-
..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%:
.%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%::
.:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-::
.*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=:
-@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+:
%@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+-
*@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#-
:%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%-
:#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%*
:-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*%
:=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+
-:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*%
-=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+
-=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%-
-+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
