#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
using namespace std;
const int inf = 1<<30, maxn = 1<<18;
using rc = array<int, 4>;
using pt = array<int, 2>;
int n, k;
vector<int> cx, cy;
bool isect(pt x, int y) {
return x[0] <= y && y <= x[1];
}
bool isect(rc x, pt y) {
return isect({x[0], x[2]}, y[0]) && isect({x[1], x[3]}, y[1]);
}
pt com(pt x, pt y) {
return {max(x[0], y[0]), min(x[1], y[0])};
}
bool empty(pt x) {
return x[0] > x[1];
}
rc bounds(vector<rc> r) {
rc b = {0, 0, 3*n, 3*n};
for(auto t : r)
for(int j = 0; j < 4; j++)
b[j] = (j < 2 ? max(b[j], t[j]) : min(b[j], t[j]));
return b;
}
void suicide(vector<pt> r) {
while(r.size() < k) r.push_back({1, 1});
for(auto &i : r) cout << cx[i[0]] << " " << cy[i[1]] << '\n';
exit(0);
}
pair<int, int> info(rc r, rc b) {
int c = 0, e = 0;
for(int i = 0; i < 4; i++) {
e |= isect({r[0+(i&1)], r[2+(i&1)]}, b[i])<<i;
c |= isect(r, {b[(i&1)*2], b[1+(i&2)]})<<i;
}
return {c, e};
}
vector<rc> split(vector<rc> r, pt f) {
for(int i = r.size(); i--;) {
if(isect(r[i], f)) swap(r[i], r.back()), r.pop_back();
}
return r;
}
multiset<int> Ll, Lr, Tl, Tr, Bl, Br;
pt Ts[maxn], Bs[maxn];
vector<pt> Ms, Mss, Msp;
map<int, vector<array<int, 3>>> ev;
void hell(vector<rc> r) {
pt g = {-inf, inf};
rc b = bounds(r);
if(b[0] <= b[2] || b[1] <= b[3]) return;
for(int i = 0; i < maxn; i++) Ts[i] = Bs[i] = {-inf, inf};
for(auto &i : r) {
i[0] = max(i[0], b[2]);
i[2] = min(i[2], b[0]);
i[1] = max(i[1], b[3]);
i[3] = min(i[3], b[1]);
auto [c, e] = info(i, b);
if(c&(c-1)) continue;
if(c == 1) {
ev[i[2]+1].push_back({2, i[0], i[2]});
} else if(c == 4) {
ev[b[0]].push_back({3, i[0], i[2]});
ev[i[0]].push_back({-3, i[0], i[2]});
} else if(int c = isect({i[0], i[2]}, b[0])*2 + isect({i[0], i[2]}, b[2]); c) {
if(c == 1) {
Ll.insert(i[1]);
Lr.insert(i[3]);
} else if(c == 3) {
ev[b[0]].push_back({1, i[1], i[3]});
ev[i[0]].push_back({-1, i[1], i[3]});
ev[i[2]+1].push_back({1, i[1], i[3]});
} else
g = com(g, {i[1], i[3]});
} else if(c == 2 || c == 8) {
if(c == 8) swap(Ts, Bs);
Ts[i[0]-1] = com(Ts[i[0]-1], {i[1], i[2]});
if(c == 8) swap(Ts, Bs);
} else if(int c = isect({i[1], i[3]}, b[1])*2 + isect({i[1], i[3]}, b[3]); c) {
if(c == 3) {
Ms.push_back({i[0], i[2]});
} else {
(c == 1 ? Bl : Tl).insert(i[0]);
(c == 1 ? Br : Tr).insert(i[2]);
}
}
}
for(int i = 1; i < maxn; i++)
Ts[i] = com(Ts[i], Ts[i-1]),
Bs[i] = com(Bs[i], Bs[i-1]);
sort(all(Ms));
Mss = Msp = Ms;
for(int i = 1; i < Ms.size(); i++) Msp[i] = com(Msp[i], Msp[i-1]);
for(int i = (int)Ms.size()-1; i--;) Mss[i] = com(Mss[i+1], Mss[i]);
int p, q;
for(auto i : ev) {
for(auto [t, l, r] : i.second) {
if(t > 0) {
(t == 1 ? Ll : (t == 2 ? Tl : Bl)).insert(l);
(t == 1 ? Lr : (t == 2 ? Tr : Br)).insert(r);
} else {
(t == 1 ? Ll : (t == 2 ? Tl : Bl)).erase((t == 1 ? Ll : (t == 2 ? Tl : Bl)).find(l));
(t == 1 ? Lr : (t == 2 ? Tr : Br)).erase((t == 1 ? Lr : (t == 2 ? Tr : Br)).find(r));
}
}
//case 1 has the leftmost thing
for(int I = 2; I--;) {
auto [sLl, sLr] = Ll.empty() ? pt{b[3], b[1]} : pt{*Ll.rbegin(), *Lr.begin()};
auto [sTl, sTr] = Tl.empty() ? pt{b[2], b[0]} : pt{*Tl.rbegin(), *Tr.begin()};
auto [sBl, sBr] = Bl.empty() ? pt{b[2], b[0]} : pt{*Bl.rbegin(), *Br.begin()};
if(i.first < g[0] || i.first > g[1] || sLl > sLr || sTl > sTr || sBl > sBr) continue;
p = Ms.size();
for(int i = 1<<19; i>>=1;)
if(p-i >= 0 && !empty(com(Mss[p-i], {sTl, sTr}))) p -= i;
if(p == 0 || !empty(com(Msp[p-1], {sBl, sBr}))) {
pt br = com(Msp[p-1], {sBl, sBr});
pt tr = com(Mss[p], {sTl, sTr});
if(empty(br)||empty(tr)) {}
else {
pt lr = com({sLl, sLr}, com(Ts[tr[0]-1], Bs[br[0]-1]));
if(!empty(lr)) {
vector<rc> ans;
ans.push_back({b[0], i.first});
ans.push_back({b[1], tr[0]});
ans.push_back({b[3], br[0]});
ans.push_back({b[2], lr[0]});
}
}
}
swap(Ts, Bs);
swap(Tl, Bl), swap(Tr, Br);
swap(b[0], b[1]), swap(b[2], b[3]);
}
}
}
int K;
void gay(vector<rc> r, int k, vector<pt> ans) {
if(r.empty() && ans.size() <= K) suicide(ans);
if(k == 0) return;
rc b = bounds(r);
if(b[0] <= b[2] || b[1] <= b[3]) {
int rev = 0;
if(b[0] > b[2]) {
swap(b[0], b[1]), swap(b[2], b[3]);
for(auto &b : r)
swap(b[0], b[1]), swap(b[2], b[3]);
}
vector<pt> segs;
for(auto [l, d, r, u] : r) segs.push_back({d, u});
sort(all(segs), greater<>());
int c = inf;
for(auto i : segs) {
if(i[1] < c) {
c = i[0];
ans.push_back(rev ? pt{i[0], b[0]} : pt{b[0], i[0]});
}
}
if(ans.size() <= K)
suicide(ans);
if(rev) {
swap(b[0], b[1]), swap(b[2], b[3]);
for(auto &b : r)
swap(b[0], b[1]), swap(b[2], b[3]);
}
}
for(int i = 0; i < 4; i++) {
pt P {b[2*(i&1)], b[1 + (i&2)]};
ans.push_back(P);
gay(split(r, P), k-1, ans);
ans.pop_back();
}
}
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> k;
K = k;
vector<rc> r(n);
cx = cy = {-inf, inf};
for(auto &i : r)
for(int j = 0; j < 4; j++) cin >> i[j], (j%2 ? cy : cx).push_back(i[j]);
for(auto *i : {&cx, &cy})
sort(i->begin(), i->end());
for(auto &i : r)
for(int j = 0; j < 4; j++) {
i[j] = lower_bound(all(cx), i[j]) - cx.begin();
swap(cx, cy);
}
if(k == 4) hell(r);
gay(r, k, {});
return 0;
}
Compilation message
hamburg.cpp: In function 'void suicide(std::vector<std::array<int, 2> >)':
hamburg.cpp:29:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
29 | while(r.size() < k) r.push_back({1, 1});
| ~~~~~~~~~^~~
hamburg.cpp: In function 'void hell(std::vector<std::array<int, 4> >)':
hamburg.cpp:96:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
96 | for(int i = 1; i < Ms.size(); i++) Msp[i] = com(Msp[i], Msp[i-1]);
| ~~^~~~~~~~~~~
hamburg.cpp:98:9: warning: unused variable 'q' [-Wunused-variable]
98 | int p, q;
| ^
hamburg.cpp: In function 'void gay(std::vector<std::array<int, 4> >, int, std::vector<std::array<int, 2> >)':
hamburg.cpp:141:29: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
141 | if(r.empty() && ans.size() <= K) suicide(ans);
| ~~~~~~~~~~~^~~~
hamburg.cpp:161:17: warning: comparison of integer expressions of different signedness: 'std::vector<std::array<int, 2> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
161 | if(ans.size() <= K)
| ~~~~~~~~~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
3 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
345 ms |
13360 KB |
Output is correct |
| 6 |
Correct |
341 ms |
13348 KB |
Output is correct |
| 7 |
Correct |
361 ms |
13360 KB |
Output is correct |
| 8 |
Correct |
366 ms |
13344 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
512 KB |
Output is correct |
| 2 |
Correct |
5 ms |
512 KB |
Output is correct |
| 3 |
Correct |
3 ms |
512 KB |
Output is correct |
| 4 |
Correct |
3 ms |
512 KB |
Output is correct |
| 5 |
Correct |
339 ms |
14628 KB |
Output is correct |
| 6 |
Correct |
348 ms |
14632 KB |
Output is correct |
| 7 |
Correct |
352 ms |
14636 KB |
Output is correct |
| 8 |
Correct |
368 ms |
15136 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
512 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
544 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
