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 <assert.h>
#include <stdio.h>
#include <stdlib.h>
#define N 200000
#define LN 18 /* N_ = pow2(ceil(log2(N))) */
#define N_ (N * (LN + 1) + 1)
#define K 4
#define INF 0x3f3f3f3f3f3f3f3fLL
long long min(long long a, long long b) { return a < b ? a : b; }
long long max(long long a, long long b) { return a > b ? a : b; }
unsigned int X = 12345;
int rand_() {
return (X *= 3) >> 1;
}
long long xxl[N], xxr[N], yyl[N], yyr[N], xx[K], yy[K]; int n, k;
long long *zz;
void sort(int *ii, int l, int r) {
while (l < r) {
int i = l, j = l, k = r, i_ = ii[l + rand_() % (r - l)], tmp;
while (j < k)
if (zz[ii[j]] == zz[i_])
j++;
else if (zz[ii[j]] < zz[i_]) {
tmp = ii[i], ii[i] = ii[j], ii[j] = tmp;
i++, j++;
} else {
k--;
tmp = ii[j], ii[j] = ii[k], ii[k] = tmp;
}
sort(ii, l, i);
l = k;
}
}
long long *xl1, *xr1, *yl1, *yr1;
int ll_[N_], rr_[N_]; long long xxl_[N_], xxr_[N_], yyl_[N_], yyr_[N_];
int update(int t, int l, int r, int i, int i_) {
static int _ = 1;
int t_ = _++;
ll_[t_] = ll_[t], rr_[t_] = rr_[t], xxl_[t_] = min(xxl_[t], xxr[i_]), xxr_[t_] = max(xxr_[t], xxl[i_]), yyl_[t_] = min(yyl_[t], yyr[i_]), yyr_[t_] = max(yyr_[t], yyl[i_]);
if (r - l > 1) {
int m = (l + r) / 2;
if (i < m)
ll_[t_] = update(ll_[t_], l, m, i, i_);
else
rr_[t_] = update(rr_[t_], m, r, i, i_);
}
return t_;
}
void query(int t, int l, int r, int ql, int qr) {
int m;
if (qr <= l || r <= ql || t == 0)
return;
if (ql <= l && r <= qr) {
*xl1 = min(*xl1, xxl_[t]), *xr1 = max(*xr1, xxr_[t]), *yl1 = min(*yl1, yyl_[t]), *yr1 = max(*yr1, yyr_[t]);
return;
}
m = (l + r) / 2;
query(ll_[t], l, m, ql, qr), query(rr_[t], m, r, ql, qr);
}
int pierced(int i, int h_) {
int h;
for (h = 0; h < h_; h++)
if (xxl[i] <= xx[h] && xx[h] <= xxr[i] && yyl[i] <= yy[h] && yy[h] <= yyr[i])
return 1;
return 0;
}
void solve(int h_) {
int h, i;
long long xl, xr, yl, yr;
xl = INF, xr = -1, yl = INF, yr = -1;
for (i = 0; i < n; i++)
if (!pierced(i, h_))
xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]);
if (xl == INF) {
for (h = h_; h < k; h++)
xx[h] = 1, yy[h] = 1;
for (h = 0; h < k; h++)
printf("%lld %lld\n", xx[h], yy[h]);
exit(0);
} else if (h_ < k) {
xx[h_] = xl, yy[h_] = yl, solve(h_ + 1);
xx[h_] = xl, yy[h_] = yr, solve(h_ + 1);
xx[h_] = xr, yy[h_] = yl, solve(h_ + 1);
xx[h_] = xr, yy[h_] = yr, solve(h_ + 1);
}
}
long long ll[N], rr[N], rr2[3][N]; int rr1[N];
int ii[3][N], nn[3], nn_[3], tt[3][N + 1]; long long xl, xr, yl, yr, z1, z2, z3, z4;
void query_(int g, long long l, long long r) {
int lower, upper, l_, r_;
lower = -1, upper = nn[g];
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (ll[ii[g][i]] >= l)
upper = i;
else
lower = i;
}
l_ = upper;
lower = -1, upper = nn_[g];
while (upper - lower > 1) {
int i = (lower + upper) / 2;
if (rr2[g][i] <= r)
lower = i;
else
upper = i;
}
r_ = upper;
query(tt[g][l_], 0, nn_[g], 0, r_);
}
void query1(long long *xx, int n, int g) {
static int ii_[K + 2];
int i;
for (i = 0; i < n; i++)
ii_[i] = i;
zz = xx, sort(ii_, 0, n);
for (i = 0; i + 1 < n; i++)
query_(g, xx[ii_[i]] + 1, xx[ii_[i + 1]] - 1);
}
long long idx(long long x, long long y) {
if (y == yl)
return x - xl;
if (x == xr)
return z1 + y - yl;
if (y == yr)
return z2 + xr - x;
if (x == xl)
return z3 + yr - y;
return -1;
}
void get_bounds(int h_) {
static long long xx_[K + 2];
int h;
long long x_;
if (h_ == 0) {
*xl1 = xl, *xr1 = xr, *yl1 = yl, *yr1 = yr;
return;
}
*xl1 = INF, *xr1 = -1, *yl1 = INF, *yr1 = -1;
xx_[0] = -1;
x_ = z4;
for (h = 0; h < h_; h++)
x_ = min(x_, xx_[h + 1] = idx(xx[h], yy[h]));
xx_[h_ + 1] = x_ + z4;
query1(xx_, h_ + 2, 0);
xx_[0] = -1;
for (h = 0; h < h_; h++)
xx_[h + 1] = xx[h];
xx_[h_ + 1] = INF;
query1(xx_, h_ + 2, 1);
xx_[0] = -1;
for (h = 0; h < h_; h++)
xx_[h + 1] = yy[h];
xx_[h_ + 1] = INF;
query1(xx_, h_ + 2, 2);
}
void solve_(int h_) {
int h, i;
long long xl_, yl_, xr_, yr_;
if (h_ > 0 && idx(xx[h_ - 1], yy[h_ - 1]) == -1)
return;
xl1 = &xl_, xr1 = &xr_, yl1 = &yl_, yr1 = &yr_, get_bounds(h_);
if (xl_ == INF) {
for (h = h_; h < k; h++)
xx[h] = 1, yy[h] = 1;
for (h = 0; h < k; h++)
printf("%lld %lld\n", xx[h], yy[h]);
exit(0);
} else if (h_ == 0) {
xx[h_] = xl_;
for (i = 0; i < n; i++)
yy[h_] = yyl[i], solve_(h_ + 1);
} else if (h_ < k) {
xx[h_] = xl_, yy[h_] = yl_, solve_(h_ + 1);
xx[h_] = xl_, yy[h_] = yr_, solve_(h_ + 1);
xx[h_] = xr_, yy[h_] = yl_, solve_(h_ + 1);
xx[h_] = xr_, yy[h_] = yr_, solve_(h_ + 1);
}
}
int main() {
int g, i, i_;
long long l, r;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++)
scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[i]);
solve(0);
xl = INF, xr = -1, yl = INF, yr = -1;
for (i = 0; i < n; i++)
xl = min(xl, xxr[i]), xr = max(xr, xxl[i]), yl = min(yl, yyr[i]), yr = max(yr, yyl[i]);
assert(k == 4 && xl < xr && yl < yr);
z1 = xr - xl, z2 = z1 + yr - yl, z3 = z2 + xr - xl, z4 = z3 + yr - yl;
for (i = 0; i < n; i++)
xxl[i] = max(xxl[i], xl), xxr[i] = min(xxr[i], xr), yyl[i] = max(yyl[i], yl), yyr[i] = min(yyr[i], yr);
for (i = 0; i < n; i++)
if (xl < xxl[i] && xxr[i] < xr && yyl[i] == yl && yyr[i] == yr)
ll[i] = xxl[i], rr[i] = xxr[i], ii[1][nn[1]++] = i;
else if (yl < yyl[i] && yyr[i] < yr && xxl[i] == xl && xxr[i] == xr)
ll[i] = yyl[i], rr[i] = yyr[i], ii[2][nn[2]++] = i;
else {
l = INF, r = -1;
if (yyl[i] == yl)
l = min(l, xxl[i] - xl), r = max(r, xxr[i] - xl);
if (xxr[i] == xr)
l = min(l, z1 + yyl[i] - yl), r = max(r, z1 + yyr[i] - yl);
if (xxl[i] == xl && yyl[i] == yl)
l += z4, r += z4;
if (yyr[i] == yr)
l = min(l, z2 + xr - xxr[i]), r = max(r, z2 + xr - xxl[i]);
if (xxl[i] == xl)
l = min(l, z3 + yr - yyr[i]), r = max(r, z3 + yr - yyl[i]);
if (l >= z4)
l -= z4, r -= z4;
ll[i] = l, rr[i] = r, ii[0][nn[0]++] = i;
}
xxl_[0] = INF, xxr_[0] = -1, yyl_[0] = INF, yyr_[0] = -1;
for (g = 0; g < 3; g++) {
zz = rr, sort(ii[g], 0, nn[g]);
for (i = 0; i < nn[g]; i++) {
i_ = ii[g][i];
rr1[i_] = nn_[g];
if (i + 1 == nn[g] || rr[ii[g][i + 1]] != rr[i_])
rr2[g][nn_[g]++] = rr[i_];
}
zz = ll, sort(ii[g], 0, nn[g]);
for (i = nn[g] - 1; i >= 0; i--) {
i_ = ii[g][i];
tt[g][i] = update(tt[g][i + 1], 0, nn_[g], rr1[i_], i_);
}
}
solve_(0);
return 0;
}
Compilation message (stderr)
hamburg.c: In function 'main':
hamburg.c:216:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
216 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
hamburg.c:218:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
218 | scanf("%lld%lld%lld%lld", &xxl[i], &yyl[i], &xxr[i], &yyr[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# | 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... |