#include <bits/stdc++.h>
using namespace std;
struct point {
int x,y,idx,pos;
};
struct rect {
int x1,y1,x2,y2;
int n1 = -1;
int n2 = -1;
long long int s1 = (long long int) 1e15;
long long int s2 = (long long int) 1e15;
int b1 = -1;
int b2 = -1;
};
bool comp(point &a, point &b){
if (a.x == b.x){
if (a.y == b.y){
return a.pos < b.pos;
}
return a.y > b.y;
}
return a.x < b.x;
}
int dist(int x1, int y1, int x2, int y2){
return abs(x1-x2) + abs(y1-y2);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int x,y;
cin >> x >> y;
int n;
cin >> n;
vector<point> points;
vector<rect> rects;
rect temp;
point t2;
int cnt = 0;
for (int i =0; i < n; i++){
cin >> temp.x1 >> temp.y1 >> temp.x2 >> temp.y2;
if (temp.x1 >= x){
continue;
}
temp.x2 = min(temp.x2,x-1);
rects.push_back(temp);
points.push_back(t2);
points.push_back(t2);
// cnt++;
points[2*cnt].x = temp.x1-1;
points[2*cnt].y = temp.y1-1;
points[2*cnt].idx = cnt;
points[2*cnt].pos = 0;
points[2*cnt+1].x = temp.x2+1;
points[2*cnt+1].y = temp.y2+1;
points[2*cnt+1].idx = cnt;
points[2*cnt+1].pos = 1;
cnt++;
}
temp.x1 = x;
temp.x2 = x;
temp.y1 = y;
temp.y2 = y;
rects.push_back(temp);
points.push_back(t2);
points.push_back(t2);
n = (int) rects.size();
points[2*n-2].x = temp.x1;
points[2*n-2].y = temp.y1;
points[2*n-2].idx = (int) (rects.size())-1;
points[2*n-2].pos = 0;
points[2*n-1].x = temp.x2;
points[2*n-1].y = temp.y2;
points[2*n-1].idx = (int) (rects.size())-1;
points[2*n-1].pos = 1;
sort(points.begin(),points.end(),comp);
set<pair<int,int>> all;
//cout << "\n\n";
for (int i =2*n-1; i >= 0; i--){
// cout << points[i].x << "," << points[i].y << " " << points[i].idx << " " << points[i].pos << '\n';
if (points[i].pos == 1){
auto it = all.lower_bound({rects[points[i].idx].y1,-1});
while (it != all.end() && (*it).first <= (points[i].y)-1){
if (points[(*it).second].pos == 0){
rects[points[(*it).second].idx].n1 = points[i].idx;
} else {
rects[points[(*it).second].idx].n2 = points[i].idx;
}
auto it2 = it;
it++;
all.erase(it2);
}
}
all.insert({points[i].y,i});
}
/* for (int i =0; i < n; i++){
cout << i << ": " << rects[i].x1 << "," << rects[i].y1 << " " << rects[i].x2 << "," << rects[i].y2 <<'\n';
cout << rects[i].n1 << " - " << rects[i].n2 << "\n\n";
}*/
int next;
int cidx;
int v1,v2;
for (int i =0; i < 2*n; i++){
cidx = points[i].idx;
if (points[i].pos == 0){
next = rects[cidx].n1;
} else {
next = rects[cidx].n2;
}
if (next == -1){
if (points[i].pos == 0){
rects[cidx].s1 = dist(0,0,points[i].x,points[i].y);
} else {
rects[cidx].s2 = dist(0,0,points[i].x,points[i].y);
}
continue;
}
if (points[i].pos == 0){
v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1);
v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1);
rects[cidx].s1 = min(v1,v2);
if (v1 < v2){
rects[cidx].b1 = 0;
} else {
rects[cidx].b1 = 1;
}
} else {
v1 = rects[next].s1+dist(points[i].x,points[i].y,rects[next].x1-1,rects[next].y1-1);
v2 = rects[next].s2+dist(points[i].x,points[i].y,rects[next].x2+1,rects[next].y2+1);
rects[cidx].s2 = min(v1,v2);
if (v1 < v2){
rects[cidx].b2 = 0;
} else {
rects[cidx].b2 = 1;
}
}
}
pair<int,int> rt;
vector<pair<int,int>> res;
int curr = n-1;
int cp = 0;
int cx,cy,ty,tx;
int wp;
rects[n-1].x1 += 1;
rects[n-1].y1 += 1;
// cout << "\n\n";
while (true){
// cout << curr << "," << cp << '\n';
if (cp == 0){
cx = rects[curr].x1-1;
cy = rects[curr].y1-1;
next = rects[curr].n1;
wp = rects[curr].b1;
} else {
cx = rects[curr].x2+1;
cy = rects[curr].y2+1;
next = rects[curr].n2;
wp = rects[curr].b2;
}
// cout << cx << "," << cy << " " << next << " " << wp << "\n\n";
if (next == -1){
tx = 0;
ty = 0;
} else {
tx = rects[next].x2+1;
if (wp == 0){
ty = rects[next].y1-1;
} else {
ty = rects[next].y2+1;
}
}
rt.first = tx - cx;
rt.second = 0;
res.push_back(rt);
rt.first = 0;
rt.second = ty - cy;
res.push_back(rt);
if (wp == 0){
rt.first = rects[next].x1-1 - tx;
rt.second = 0;
res.push_back(rt);
}
if (next == -1){
break;
}
curr = next;
cp = wp;
}
/* cout << "\n\n";
for (int i =0; i < n; i++){
cout << i << ": " << rects[i].x1 << "," << rects[i].y1 << " " << rects[i].x2 << "," << rects[i].y2 <<'\n';
cout << rects[i].n1 << " - " << rects[i].n2 << "\n";
cout << rects[i].b1 << ',' << rects[i].s1 << " - " << rects[i].b2 << "," << rects[i].s2 << "\n\n";
}*/
wp = -1;
cx = 0;
cy = 0;
vector<pair<int,int>> fin;
for (int i =res.size()-1; i >= 0; i--){
if (res[i].first == 0){
if (wp == 1 || wp ==-1){
cy -= res[i].second;
wp = 1;
} else{
fin.push_back({cx,cy});
cx = 0;
cy = -1 * res[i].second;
wp = 1;
}
} else {
if (wp == 0 || wp ==-1){
cx -= res[i].first;
wp = 0;
} else{
fin.push_back({cx,cy});
cx = -1 * res[i].first;
cy = 0;
wp = 0;
}
}
}
if (wp != -1){
fin.push_back({cx,cy});
}
cout << rects[n-1].s1 << "\n";
cout << fin.size() << '\n';
for (int i =0; i < fin.size(); i++){
cout << fin[i].first << " " << fin[i].second << '\n';
}
return 0;
}
Compilation message
walk.cpp: In function 'int main()':
walk.cpp:242:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
242 | for (int i =0; i < fin.size(); i++){
| ~~^~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
348 KB |
Output is correct |
| 2 |
Correct |
1 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Correct |
1 ms |
604 KB |
Output is correct |
| 5 |
Correct |
72 ms |
9636 KB |
Output is correct |
| 6 |
Correct |
23 ms |
3552 KB |
Output is correct |
| 7 |
Correct |
43 ms |
6688 KB |
Output is correct |
| 8 |
Correct |
74 ms |
10824 KB |
Output is correct |
| 9 |
Correct |
90 ms |
10004 KB |
Output is correct |
| 10 |
Correct |
79 ms |
12248 KB |
Output is correct |
