#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int INF = 1'000'000'000;
const int X = 400005;
struct Point {
int x, y;
};
struct Seg {
int l, r;
Seg() : l(1), r(X) {}
Seg(int l, int r) : l(l), r(r) {}
};
void self_intersect(Seg &a, const Seg &b) {
a.l = max(a.l, b.l);
a.r = min(a.r, b.r);
}
Seg intersect(Seg a, const Seg &b) {
self_intersect(a, b);
return a;
}
bool inside(int x, const Seg &s) {
return x >= s.l && x <= s.r;
}
struct Rect {
Seg x, y;
Rect() : x{}, y{} {}
Rect(const Seg &x, const Seg &y) : x(x), y(y) {}
};
istream &operator>>(istream &stream, Rect &r) {
stream >> r.x.l >> r.y.l >> r.x.r >> r.y.r;
return stream;
}
void self_intersect(Rect &a, const Rect &b) {
self_intersect(a.x, b.x);
self_intersect(a.y, b.y);
}
Rect intersect(Rect a, const Rect &b) {
self_intersect(a, b);
return a;
}
bool inside(const Point &p, const Rect &r) {
return inside(p.x, r.x) && inside(p.y, r.y);
}
int adjust(int val, vector<int> &vals) {
return lower_bound(vals.begin(), vals.end(), val) - vals.begin();
}
int k;
vector<int> xs, ys;
void output(const vector<Point> &pts) {
for (const auto &[x, y] : pts) {
cout << xs[x] << " " << ys[y] << "\n";
}
exit(0);
}
void solve(const vector<Rect> &rects, const vector<Point> &pts) {
if ((int)pts.size() == k) {
if (rects.empty()) {
output(pts);
}
return;
}
Rect intersection;
for (const auto &rect : rects) {
self_intersect(intersection, rect);
}
for (int x : {intersection.x.l, intersection.x.r}) {
for (int y : {intersection.y.l, intersection.y.r}) {
Point p = {x, y};
auto npts = pts;
npts.push_back(p);
vector<Rect> nrects;
for (const auto &rect : rects) {
if (!inside(p, rect)) {
nrects.push_back(rect);
}
}
solve(nrects, npts);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n >> k;
vector<Rect> rects(n);
for (auto &r : rects) {
cin >> r;
}
xs.push_back(0);
ys.push_back(0);
xs.push_back(INF + 1);
ys.push_back(INF + 1);
for (const auto &r : rects) {
xs.push_back(r.x.l);
xs.push_back(r.x.r);
ys.push_back(r.y.l);
ys.push_back(r.y.r);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
while (X <= (int)xs.size()) {
xs.push_back(xs.back());
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
while (X <= (int)ys.size()) {
ys.push_back(ys.back());
}
for (auto &r : rects) {
adjust(r.x.l, xs);
adjust(r.y.l, ys);
adjust(r.x.r, xs);
adjust(r.y.r, ys);
}
solve(rects, vector<Point>{});
Rect intersection;
for (const auto &r : rects) {
self_intersect(intersection, r);
}
int dy = intersection.y.r, uy = intersection.y.l;
int lx = intersection.x.r, rx = intersection.x.l;
Seg base_sd, base_su, base_sl, base_sr;
vector<Seg> pref_dl(X + 1);
vector<Seg> suff_dr(X + 1);
vector<Seg> pref_du(X + 1);
vector<Seg> suff_du(X + 1);
vector<Seg> pref_lr(X + 1);
vector<Seg> suff_lr(X + 1);
vector<Seg> suff_lu(X + 1);
vector<Seg> suff_ru(X + 1);
for (const auto &r : rects) {
int fd = inside(dy, r.y);
int fu = inside(uy, r.y);
int fl = inside(lx, r.x);
int fr = inside(rx, r.x);
if (fd + fu + fl + fr > 2) {
continue;
}
if (fd + fu + fl + fr == 0) {
assert(0);
}
if (fd + fu + fl + fr == 1) {
if (fd) {
self_intersect(base_sd, r.x);
} else if (fu) {
self_intersect(base_su, r.x);
} else if (fl) {
self_intersect(base_sl, r.y);
} else {
self_intersect(base_sr, r.y);
}
} else {
if (fd && fu) {
self_intersect(pref_du[r.x.r], r.x);
self_intersect(suff_du[r.x.l], r.x);
} else if (fd && fl) {
self_intersect(pref_dl[r.x.r], r.y);
} else if (fd && fr) {
self_intersect(suff_dr[r.x.l], r.y);
} else if (fl && fr) {
self_intersect(pref_lr[r.y.r], r.y);
self_intersect(suff_lr[r.y.l], r.y);
} else if (fu && fl) {
self_intersect(suff_lu[r.y.r], r.x);
} else {
self_intersect(suff_ru[r.y.r], r.x);
}
}
}
for (int i = 0; i < X; ++i) {
self_intersect(pref_lr[i + 1], pref_lr[i]);
self_intersect(pref_dl[i + 1], pref_dl[i]);
self_intersect(pref_du[i + 1], pref_du[i]);
}
for (int i = X; i > 0; --i) {
self_intersect(suff_dr[i - 1], suff_dr[i]);
self_intersect(suff_du[i - 1], suff_du[i]);
self_intersect(suff_lu[i - 1], suff_lu[i]);
self_intersect(suff_ru[i - 1], suff_ru[i]);
self_intersect(suff_lr[i - 1], suff_lr[i]);
}
for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
Seg su = base_su, sl = base_sl, sr = base_sr;
self_intersect(sl, pref_dl[dx - 1]);
self_intersect(sr, suff_dr[dx + 1]);
self_intersect(su, pref_du[dx - 1]);
self_intersect(su, suff_du[dx + 1]);
int ly = pref_lr[X].r;
if (!inside(ly, sl)) {
continue;
}
self_intersect(sr, pref_lr[ly - 1]);
self_intersect(sr, suff_lr[ly + 1]);
if (sr.l > sr.r) {
continue;
}
int ry = sr.r;
self_intersect(su, suff_lu[ly + 1]);
self_intersect(su, suff_ru[ry + 1]);
if (su.l > su.r) {
continue;
}
int ux = su.l;
output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
}
for (int dx = base_sd.l; dx <= base_sd.r; ++dx) {
Seg su = base_su, sl = base_sl, sr = base_sr;
self_intersect(sl, pref_dl[dx - 1]);
self_intersect(sr, suff_dr[dx + 1]);
self_intersect(su, pref_du[dx - 1]);
self_intersect(su, suff_du[dx + 1]);
int ry = pref_lr[X].r;
if (!inside(ry, sr)) {
continue;
}
self_intersect(sl, pref_lr[ry - 1]);
self_intersect(sl, suff_lr[ry + 1]);
if (sl.l > sl.r) {
continue;
}
int ly = sl.r;
self_intersect(su, suff_lu[ly + 1]);
self_intersect(su, suff_ru[ry + 1]);
if (su.l > su.r) {
continue;
}
int ux = su.l;
output(vector<Point>{Point{dx, dy}, Point{lx, ly}, Point{rx, ry}, Point{ux, uy}});
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
716 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
588 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
