This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define Fi first
#define Se second
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define szz(x) (int)(x).size()
#define rep(i, n) for(int i=0;i<(n);i++)
typedef tuple<int, int, int> t3;
const int INF = 1e9 + 10, M = 4e5 + 5;
pii operator+(pii a, pii b) { return {max(a.Fi, b.Fi), min(a.Se, b.Se)}; }
int N, K;
vector <int> vx, vy;
struct rect {
int x1, y1, x2, y2;
bool In(int x, int y) {
return x1 <= x && x <= x2 && y1 <= y && y <= y2;
}
} R[200020];
void trial(vector <pii> ans, int flp = 0) {
if(szz(ans) == 0 || szz(ans) > K) return;
while(szz(ans) < K) ans.pb(ans[0]);
for(int i=1;i<=N;i++) {
int r = 0;
for(auto &[x, y] : ans) if(R[i].In(x, y)) {
r = 1; break;
}
if(r == 0) return;
}
for(auto [x, y] : ans) {
if(flp) y = szz(vy) + 1 - y;
printf("%d %d\n", vx[x-1], vy[y-1]);
}
exit(0);
}
int arr[4*M+5];
vector <int> solve_linear(vector <pii> R) {
for(int i=1;i<=M;i++) arr[i] = INF;
for(auto [x, y] : R) arr[x] = min(arr[x], y);
for(int i=M-1;i;i--) arr[i] = min(arr[i], arr[i+1]);
vector <int> res;
for(int t=1;arr[t]!=INF;t=arr[t]+1) res.pb(arr[t]);
return res;
}
pii seg[6][2][M+5];
void solve(vector <int> rst, int k, vector <pii> ans) {
if(szz(rst) == 0) trial(ans);
if(k == 0) return;
int lx = INF, rx = -INF, ly = INF, ry = -INF;
for(int i : rst) {
lx = min(lx, R[i].x2);
rx = max(rx, R[i].x1);
ly = min(ly, R[i].y2);
ry = max(ry, R[i].y1);
}
if(k == 1) {
if(lx >= rx && ly >= ry) {
ans.pb({rx, ry});
trial(ans);
}
return;
}
if(lx >= rx) {
vector <pii> V;
for(int i : rst) V.pb({R[i].y1, R[i].y2});
auto ys = solve_linear(V);
for(int y : ys) ans.pb({rx, y});
trial(ans);
return;
}
if(ly >= ry) {
vector <pii> V;
for(int i : rst) V.pb({R[i].x1, R[i].x2});
auto xs = solve_linear(V);
for(int x : xs) ans.pb({x, ry});
trial(ans);
return;
}
vector <pii> vert;
for(int x : {lx, rx}) for(int y : {ly, ry}) vert.pb({x, y});
for(auto [x, y] : vert) {
vector <int> nst;
for(int i : rst) if(!R[i].In(x, y)) nst.pb(i);
auto ans2 = ans; ans2.pb({x, y});
solve(nst, k - 1, ans2);
}
if(k != 4) return;
auto fy = [&](int &y) { y = szz(vy) + 1 - y; };
auto Intersect = [&](const rect &a, const rect &b) {
pii x = pii(a.x1, a.x2) + pii(b.x1, b.x2);
if(x.Fi > x.Se) return 0;
pii y = pii(a.y1, a.y2) + pii(b.y1, b.y2);
if(y.Fi > y.Se) return 0;
return 1;
};
auto solve4 = [&](int flp) {
rect Side[4];
Side[0] = {lx, ly, lx, ry};
Side[1] = {lx, ry, rx, ry};
Side[2] = {rx, ly, rx, ry};
Side[3] = {lx, ly, rx, ly};
auto type = [&](int t) {
int res = 0;
rep(i, 4) if(Intersect(R[t], Side[i])) res |= 1<<i;
return res;
};
pii Seg[4];
Seg[0] = Seg[2] = {ly, ry};
Seg[1] = Seg[3] = {lx, rx};
auto upd = [&](pii &a, pii b) { a = a + b; };
rep(i, 6) rep(j, 2) rep(k, M+1) seg[i][j][k] = pii(-INF, INF);
int nrx = INF;
for(int i=1;i<=N;i++) {
int t = type(i);
pii wx = {R[i].x1, R[i].x2}, wy = {R[i].y1, R[i].y2};
if(t == 1) upd(Seg[0], wy);
else if(t == 2) upd(Seg[1], wx);
else if(t == 4) upd(Seg[2], wy);
else if(t == 8) upd(Seg[3], wx);
else if(t == 3) upd(seg[0][0][R[i].y1-1], wx);
else if(t == 5) {
upd(seg[1][0][R[i].y1-1], wy);
upd(seg[1][1][R[i].y2+1], wy);
}
else if(t == 9) upd(seg[2][1][R[i].y2+1], wx);
else if(t == 6) upd(seg[3][0][R[i].x1-1], wy);
else if(t == 10) {
upd(seg[4][0][R[i].x1-1], wx);
upd(seg[4][1][R[i].x2+1], wx);
nrx = min(nrx, R[i].x2);
}
}
rep(i, 6) {
for(int j=M-1;j;j--) upd(seg[i][0][j], seg[i][0][j+1]);
for(int j=2;j<=M;j++) upd(seg[i][1][j], seg[i][1][j-1]);
for(int j=1;j<=M;j++) upd(seg[i][0][j], seg[i][1][j]);
}
vector <pii> ans(4);
for(int i=ly+1;i<ry;i++) {
ans[0] = {lx, i};
pii NS[3];
rep(j, 3) NS[j] = Seg[j+1] + seg[j][0][i];
int ri = min({nrx, NS[0].Se, NS[2].Se});
if(NS[0].Fi > NS[0].Se) continue;
ans[1] = {ri, ry};
upd(NS[1], seg[3][0][ri]);
upd(NS[2], seg[4][0][ri]);
if(NS[1].Fi > NS[1].Se) continue;
int rj = NS[1].Fi;
ans[2] = {rx, rj};
upd(NS[2], seg[5][0][rj]);
if(NS[2].Fi > NS[2].Se) continue;
ans[3] = {NS[2].Se, ly};
trial(ans);
}
};
solve4(0);
for(int i=1;i<=N;i++) fy(R[i].y1), fy(R[i].y2);
swap(ly, ry); fy(ly), fy(ry);
solve4(1);
}
int main() {
scanf("%d%d", &N, &K);
for(int i=1;i<=N;i++) {
scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
vx.pb(R[i].x1), vx.pb(R[i].x2);
vy.pb(R[i].y1), vy.pb(R[i].y2);
}
sort(all(vx)); vx.resize(unique(all(vx)) - vx.begin());
sort(all(vy)); vy.resize(unique(all(vy)) - vy.begin());
for(int i=1;i<=N;i++) {
auto &[x1, y1, x2, y2] = R[i];
x1 = (int)(lower_bound(all(vx), x1) - vx.begin()) + 1;
y1 = (int)(lower_bound(all(vy), y1) - vy.begin()) + 1;
x2 = (int)(lower_bound(all(vx), x2) - vx.begin()) + 1;
y2 = (int)(lower_bound(all(vy), y2) - vy.begin()) + 1;
}
vector <int> rst;
for(int i=1;i<=N;i++) rst.pb(i);
solve(rst, K, {});
return 0;
}
Compilation message (stderr)
hamburg.cpp: In function 'int main()':
hamburg.cpp:175:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
175 | scanf("%d%d", &N, &K);
| ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:177:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
177 | scanf("%d%d%d%d", &R[i].x1, &R[i].y1, &R[i].x2, &R[i].y2);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |