#include <bits/stdc++.h>
using namespace std;
const int N = 200000, X = 1000000000;
vector<array<int, 2>> ans;
array<int, 4> rect[N];
bool tested[N];
int n, k;
vector<int> adj[N], jda[N], order;
int color[N], s, m;
bool visited[N];
void add_expr(int u, int v) {
adj[u ^ 1].push_back(v);
adj[v ^ 1].push_back(u);
jda[u].push_back(v ^ 1);
jda[v].push_back(u ^ 1);
}
struct side {
map<int, int> map, prefix, suffix;
void add(int x) {
if (map.count(x) == 0) {
suffix[x] = m + 4;
prefix[x] = m + 2;
map[x] = m;
m += 6;
}
}
int less(int x) {
add(x);
return prefix[x];
}
int greater(int x) {
add(x);
return suffix[x];
}
void init() {
vector<pair<int, int>> pairs(map.begin(), map.end());
for (int i = 1; i < (int) pairs.size(); ++i) {
int x = pairs[i - 1].first, y = pairs[i].first;
add_expr(prefix[x] ^ 1, suffix[y] ^ 1);
add_expr(prefix[x] ^ 1, map[y] ^ 1);
add_expr(map[x] ^ 1, suffix[y] ^ 1);
}
}
int find() {
for (auto [x, y] : map) {
if (color[y] > color[y + 1]) {
return x;
}
}
return -1;
}
};
array<int, 4> bounds() {
int x1 = X, x2 = 0, y1 = X, y2 = 0;
for (int i = 0; i < n; ++i) {
auto [l, d, r, u] = rect[i];
if (!tested[i]) {
x1 = min(x1, r);
x2 = max(x2, l);
y1 = min(y1, u);
y2 = max(y2, d);
}
}
return {x1, x2, y1, y2};
}
void solve() {
if (count(tested, tested + n, false) == 0) {
while ((int) ans.size() < k) {
ans.push_back(ans.back());
}
for (auto [x, y] : ans) {
cout << x << " " << y << "\n";
}
exit(0);
} else if ((int) ans.size() == k) {
return;
}
auto [x1, x2, y1, y2] = bounds();
for (auto x : {x1, x2}) {
for (auto y : {y1, y2}) {
ans.push_back({x, y});
vector<int> undo;
for (int i = 0; i < n; ++i) {
auto [l, d, r, u] = rect[i];
if (!tested[i] && l <= x && x <= r && d <= y && y <= u) {
undo.push_back(i);
tested[i] = true;
}
}
solve();
for (auto i : undo) {
tested[i] = false;
}
ans.pop_back();
}
}
}
void dfs_order(int u) {
visited[u] = true;
for (auto c : adj[u]) {
if (!visited[c]) {
dfs_order(c);
}
}
order.push_back(u);
}
void dfs_color(int u, int x) {
color[u] = x;
for (auto c : jda[u]) {
if (color[c] != 0) {
dfs_color(c, x);
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 0; i < n; ++i) {
for (auto &j : rect[i]) {
cin >> j;
}
}
solve();
auto [x1, x2, y1, y2] = bounds();
side left, down, right, up;
for (int i = 0; i < n; ++i) {
auto [l, d, r, u] = rect[i];
if (!(l <= x1 && x2 <= r) && !(d <= y1 && y2 <= u)) {
if (l <= x1 && d <= y1) {
add_expr(left.less(u), down.less(r));
} else if (l <= x1 && u >= y2) {
add_expr(left.greater(d), up.less(r));
} else if (r >= x2 && d <= y1) {
add_expr(right.less(u), down.greater(l));
} else if (r >= x2 && u >= y2) {
add_expr(right.greater(d), up.greater(l));
} else if (l <= x1) {
add_expr(left.greater(d), left.greater(d));
add_expr(left.less(u), left.less(u));
} else if (r >= x2) {
add_expr(right.greater(d), right.greater(d));
add_expr(right.less(u), right.less(u));
} else if (d <= y1) {
add_expr(down.greater(l), down.greater(l));
add_expr(down.less(r), down.less(r));
} else if (u >= y2) {
add_expr(up.greater(l), up.greater(l));
add_expr(up.less(r), up.less(r));
}
}
}
left.init();
down.init();
right.init();
up.init();
for (int i = 0; i < m; ++i) {
if (!visited[i]) {
dfs_order(i);
}
}
reverse(order.begin(), order.end());
for (auto i : order) {
if (color[i] == 0) {
dfs_color(i, ++s);
}
}
cout << x1 << " " << left.find() << "\n";
cout << down.find() << " " << y1 << "\n";
cout << x2 << " " << right.find() << "\n";
cout << up.find() << " " << y2 << "\n";
}
Compilation message
hamburg.cpp:23:19: error: declaration of 'std::map<int, int> side::map' changes meaning of 'map' [-fpermissive]
23 | map<int, int> map, prefix, suffix;
| ^~~
In file included from /usr/include/c++/9/map:61,
from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:81,
from hamburg.cpp:1:
/usr/include/c++/9/bits/stl_map.h:100:11: note: 'map' declared here as 'class std::map<int, int>'
100 | class map
| ^~~
