#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>
using namespace std;
// ----- Structures for Buildings, Candidates, and Events -----
struct Building {
int r; // right coordinate = max(x1,x2)
int lower; // min(y1,y2)
int upper; // max(y1,y2)
int id; // building id (0-indexed)
};
// Candidate point: either the upper-right (TU) or lower-right (TD) corner of a building,
// or the dummy candidate for the destination.
struct Candidate {
int x, y; // grid coordinates
int type; // 0: TU, 1: TD, 2: dummy (destination)
int bID; // building id (for TU and TD); -1 for dummy
int nxt; // the "next" building id (computed by sweep–line); -1 means ε.
// DP fields:
long long dp; // best (minimum) Manhattan distance from S=(0,0) to this candidate along a special path.
int parent; // parent candidate index (for path reconstruction), or -1 if coming directly from S.
};
// An event for the sweep–line (to compute "next" for candidates).
// There are four kinds:
// type 0: Activation of building at y = building.lower
// type 1: Deactivation of building at y = building.upper
// type 2: Query for TD candidate (at y = candidate.y, which equals building.lower - 1)
// type 3: Query for TU candidate (at y = candidate.y, which equals building.upper + 1)
// (For the dummy candidate we treat it as a TU candidate.)
struct Event {
int y;
int type; // 0: activate, 1: deactivate, 2: queryTD, 3: queryTU
int x; // the x coordinate at which we update/query (this is the building's right side)
int bID; // building id (for activate/deactivate events)
int candIdx; // candidate index (for query events)
};
// ----- Segment Tree (Tournament Tree) for range maximum query -----
// We store a pair: (val, bID) where val is the x coordinate (i.e. building right coordinate)
// and bID is the building id. The merge returns the pair with larger 'val' (i.e. the right–most active building).
struct SegNode {
int val;
int bID;
};
struct SegmentTree {
int size;
vector<SegNode> tree;
SegmentTree(int n) {
size = 1;
while(size < n) size *= 2;
tree.assign(2 * size, {-1, -1});
}
// Update position pos (0-indexed) to value (val, bID)
void update(int pos, int val, int bID) {
pos += size;
tree[pos] = {val, bID};
for(pos /= 2; pos >= 1; pos /= 2) {
if(tree[2*pos].val >= tree[2*pos+1].val)
tree[pos] = tree[2*pos];
else
tree[pos] = tree[2*pos+1];
}
}
// Query the maximum in interval [l, r] (inclusive)
SegNode query(int l, int r) {
SegNode res = {-1, -1};
l += size; r += size;
while(l <= r) {
if(l % 2 == 1) {
if(tree[l].val > res.val) res = tree[l];
l++;
}
if(r % 2 == 0) {
if(tree[r].val > res.val) res = tree[r];
r--;
}
l /= 2; r /= 2;
}
return res;
}
};
// ----- Helper: Manhattan distance between two points -----
inline long long manhattan(int x1, int y1, int x2, int y2) {
return llabs(x1 - x2) + llabs(y1 - y2);
}
// ----- Main -----
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int X, Y, N;
cin >> X >> Y;
cin >> N;
vector<Building> buildings;
buildings.reserve(N);
for (int i = 0; i < N; i++){
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
int r = max(x1, x2);
int lower = min(y1, y2);
int upper = max(y1, y2);
buildings.push_back({r, lower, upper, i});
}
// ----- Build candidate points -----
// For each building, we create two candidates:
// TU: (r, upper + 1)
// TD: (r, lower - 1)
// And we also add one dummy candidate for the destination D = (X, Y).
vector<Candidate> cand;
cand.reserve(2 * N + 1);
// We will also remember, for each building, the candidate indices for TU and TD.
vector<int> candTU(N, -1), candTD(N, -1);
for (int i = 0; i < N; i++){
// Upper–right candidate (TU)
Candidate c;
c.x = buildings[i].r;
c.y = buildings[i].upper + 1;
c.type = 0; // TU
c.bID = buildings[i].id;
c.nxt = -1;
cand.push_back(c);
candTU[buildings[i].id] = cand.size() - 1;
// Lower–right candidate (TD)
c.x = buildings[i].r;
c.y = buildings[i].lower - 1;
c.type = 1; // TD
c.bID = buildings[i].id;
c.nxt = -1;
cand.push_back(c);
candTD[buildings[i].id] = cand.size() - 1;
}
// Add dummy candidate for destination D; we treat it as a TU candidate.
Candidate dummy;
dummy.x = X;
dummy.y = Y;
dummy.type = 2; // dummy
dummy.bID = -1;
dummy.nxt = -1;
cand.push_back(dummy);
int dummyIdx = cand.size() - 1;
// ----- Build events for the sweep–line (to compute candidate.nxt) -----
// For each building, add:
// Activation event at y = lower, type 0.
// Deactivation event at y = upper, type 1.
// For each candidate from a building:
// For TD (type 1): add query event at y = (lower - 1) [i.e. candidate.y], type 2.
// For TU (type 0): add query event at y = (upper + 1) [i.e. candidate.y], type 3.
// For the dummy candidate (type 2), add query event at y = Y + 1, type 3.
vector<Event> events;
events.reserve(2 * N + cand.size());
for (int i = 0; i < N; i++){
// Activation event for building i at y = lower
Event ev;
ev.y = buildings[i].lower;
ev.type = 0; // activate
ev.x = buildings[i].r;
ev.bID = buildings[i].id;
ev.candIdx = -1;
events.push_back(ev);
// Deactivation event for building i at y = upper
ev.y = buildings[i].upper;
ev.type = 1; // deactivate
ev.x = buildings[i].r;
ev.bID = buildings[i].id;
ev.candIdx = -1;
events.push_back(ev);
}
// Candidate query events:
for (int i = 0; i < (int)cand.size(); i++){
Event ev;
// For candidates from buildings:
if(cand[i].type == 0){ // TU candidate: query event type 3 at y = candidate.y (== upper+1)
ev.y = cand[i].y;
ev.type = 3; // query TU
} else if(cand[i].type == 1){ // TD candidate: query event type 2 at y = candidate.y (== lower-1)
ev.y = cand[i].y;
ev.type = 2; // query TD
} else if(cand[i].type == 2){
// For dummy candidate, treat as TU; add query event at y = Y+1.
ev.y = Y + 1;
ev.type = 3; // query TU
}
ev.x = cand[i].x; // candidate's x coordinate
ev.candIdx = i;
ev.bID = -1;
events.push_back(ev);
}
// Sort events by y; if equal, by type (we assume lower type values come first)
sort(events.begin(), events.end(), [](const Event &a, const Event &b) {
if(a.y == b.y) return a.type < b.type;
return a.y < b.y;
});
// ----- Process events with a segment tree -----
// Domain for x: x can be from 0 up to max (we assume maxX = 1000001)
const int MAXX = 1000002;
SegmentTree seg(MAXX);
// Initially, all positions are -1.
for (int i = 0; i < (int)events.size(); i++){
if(events[i].type == 0) { // Activation: add building at position events[i].x
seg.update(events[i].x, events[i].x, events[i].bID);
} else if(events[i].type == 1) { // Deactivation: remove building at position events[i].x
seg.update(events[i].x, -1, -1);
} else if(events[i].type == 2 || events[i].type == 3) { // Query events for candidate.
SegNode res = seg.query(0, events[i].x);
int found = res.val; // if -1, then no building found.
int foundBID = res.bID;
cand[events[i].candIdx].nxt = foundBID; // will be -1 if not found.
}
}
// ----- DP: compute shortest distance (and parent pointers) for each candidate.
// Our recurrence is:
// If cand.nxt == -1, then dp = cand.x + |cand.y| (distance from S = (0,0)).
// Otherwise, let r = cand.nxt (a building id) and let P1 = candidate TU for building r,
// P2 = candidate TD for building r.
// Then: dp = min( dp[P1] + d(P1, cand), dp[P2] + d(P2, cand) ).
// Since r < cand.x, these candidates come earlier when we sort by x.
// Sort candidates by (x, then y)
vector<int> order(cand.size());
for (int i = 0; i < (int)cand.size(); i++)
order[i] = i;
sort(order.begin(), order.end(), [&](int a, int b) {
if(cand[a].x == cand[b].x)
return cand[a].y < cand[b].y;
return cand[a].x < cand[b].x;
});
const long long INF = 1LL << 60;
vector<long long> dp(cand.size(), INF);
vector<int> par(cand.size(), -1);
// For quick lookup: for each building id, record the candidate indices for TU and TD.
// (They were computed earlier in candTU and candTD.)
for (int idx : order) {
// Base case: if no building is encountered when going left from this candidate.
if(cand[idx].nxt == -1) {
dp[idx] = (long long)cand[idx].x + llabs(cand[idx].y);
par[idx] = -1;
} else {
int r = cand[idx].nxt; // building id from "next"
// Use the two candidate points for building r.
int idxTU = candTU[r];
int idxTD = candTD[r];
// They must have been processed already (since their x < cand[idx].x)
long long opt1 = dp[idxTU] + manhattan(cand[idx].x, cand[idx].y, cand[idxTU].x, cand[idxTU].y);
long long opt2 = dp[idxTD] + manhattan(cand[idx].x, cand[idx].y, cand[idxTD].x, cand[idxTD].y);
if(opt1 <= opt2) {
dp[idx] = opt1;
par[idx] = idxTU;
} else {
dp[idx] = opt2;
par[idx] = idxTD;
}
}
}
// Find the dummy candidate (destination)
int destIdx = -1;
for (int i = 0; i < (int)cand.size(); i++){
if(cand[i].type == 2) {
destIdx = i;
break;
}
}
assert(destIdx != -1);
// The answer (minimum path length) is dp[destIdx]
long long ans = dp[destIdx];
// ----- Reconstruct the candidate chain (turning–points) -----
vector<int> chain;
int cur = destIdx;
while(cur != -1) {
chain.push_back(cur);
cur = par[cur];
}
// Reverse the chain so that it goes from the candidate reached directly from S up to destination.
reverse(chain.begin(), chain.end());
// Build the polyline: start with S = (0,0) then the candidate points in order.
vector<pair<int,int>> polyline;
polyline.push_back({0, 0});
for (int idx : chain)
polyline.push_back({cand[idx].x, cand[idx].y});
// ----- Compress the polyline into alternating horizontal and vertical segments -----
// (Merge consecutive segments that are collinear.)
vector<pair<int,int>> points;
points.push_back(polyline[0]);
for (int i = 1; i < (int)polyline.size(); i++){
// If the last two points and the new point are collinear (in a horizontal or vertical direction), merge.
if(points.size() >= 2) {
auto &p1 = points[points.size()-2];
auto &p2 = points[points.size()-1];
auto &p3 = polyline[i];
// Check if p1->p2 and p2->p3 are parallel
if((p2.first - p1.first == 0 && p3.first - p2.first == 0) ||
(p2.second - p1.second == 0 && p3.second - p2.second == 0)) {
points.back() = p3;
continue;
}
}
points.push_back(polyline[i]);
}
// Now, segments are differences between consecutive points in 'points'
vector<pair<int,int>> segments;
for (int i = 0; i < (int)points.size()-1; i++){
int dx = points[i+1].first - points[i].first;
int dy = points[i+1].second - points[i].second;
segments.push_back({dx, dy});
}
// ----- Output the solution -----
cout << ans << "\n";
cout << segments.size() << "\n";
for (auto &seg : segments)
cout << seg.first << " " << seg.second << "\n";
return 0;
}
| # | Verdict | Execution time | Memory | Grader output |
|---|
| Fetching results... |
