#include <stdio.h>
#include <sys/time.h>
#define N 100000
#define INF 0x3f3f3f3f3f3f3f3fLL
#define X 1000000001
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 Z = 12345;
int rand_() {
return (Z *= 3) >> 1;
}
int xx[N], yy[N], n;
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 (xx[ii[j]] == xx[i_])
j++;
else if (xx[ii[j]] < xx[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;
}
}
void solve1(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
int i, i_, x, y, xl, xr, yl, yr, s;
if (n == 0) {
if (ss_[0] > 1)
xx_[0] = X + 1, yy_[0] = X + 1, ss_[0] = 1;
return;
}
xl = X, xr = -X, yl = X, yr = -X;
for (i = 0; i < n; i++) {
i_ = ii[i], x = xx[i_], y = yy[i_];
xl = min(xl, x), xr = max(xr, x);
yl = min(yl, y), yr = max(yr, y);
}
s = max(max(xr - xl, yr - yl), 1);
if (ss_[0] > s)
xx_[0] = xl, yy_[0] = yl, ss_[0] = s;
}
void solve2(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static int ypl[N], ypr[N], yql[N], yqr[N];
int i, xl, xr, y, yl, yr;
if (n == 0) {
if (max(ss_[0], ss_[1]) > 1) {
xx_[0] = -(X + 2), yy_[0] = -(X + 2), ss_[0] = 1;
xx_[1] = X + 1, yy_[1] = -(X + 2), ss_[1] = 1;
}
return;
}
xl = xx[ii[0]], xr = xx[ii[n - 1]];
yl = X, yr = -X;
for (i = 0; i < n; i++) {
y = yy[ii[i]];
ypl[i] = yl = min(yl, y);
ypr[i] = yr = max(yr, y);
}
yl = X, yr = -X;
for (i = n - 1; i >= 0; i--) {
y = yy[ii[i]];
yql[i] = yl = min(yl, y);
yqr[i] = yr = max(yr, y);
}
for (i = -1; i < n; i++) {
long long xp, xq, x0, y0, s0, x1, y1, s1;
xp = i == -1 ? -(X + 1) : xx[ii[i]], xq = i + 1 == n ? X + 1 : xx[ii[i + 1]];
if (xp == xq)
continue;
if (i == -1)
s0 = 1, x0 = -(X + 2), y0 = -(X + 2);
else
s0 = max(max(xp - xl, ypr[i] - ypl[i]), 1), x0 = xp - s0, y0 = ypr[i] - s0;
if (i + 1 == n)
s1 = 1, x1 = X + 1, y1 = -(X + 2);
else
s1 = max(max(xr - xq, yqr[i + 1] - yql[i + 1]), 1), x1 = xq, y1 = yqr[i + 1] - s1;
if (max(ss_[0], ss_[1]) > max(s0, s1))
xx_[0] = x0, yy_[0] = y0, ss_[0] = s0, xx_[1] = x1, yy_[1] = y1, ss_[1] = s1;
}
}
void solve21(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static long long xx1[3], yy1[3], ss1[3];
static int ii1[N], ii2[N];
int n1, n2, h, i, i_, lower, upper;
lower = -X, upper = X;
while (upper - lower > 1) {
int y = (lower + upper) / 2;
n1 = n2 = 0;
for (i = 0; i < n; i++) {
i_ = ii[i];
if (yy[i_] <= y)
ii1[n1++] = i_;
else
ii2[n2++] = i_;
}
ss1[0] = ss1[1] = ss1[2] = INF;
solve2(ii1, n1, xx1, yy1, ss1), solve1(ii2, n2, xx1 + 2, yy1 + 2, ss1 + 2);
if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(ss1[0], ss1[1]), ss1[2]))
for (h = 0; h < 3; h++)
xx_[h] = xx1[h], yy_[h] = yy1[h], ss_[h] = ss1[h];
if (max(ss1[0], ss1[1]) < ss1[2])
lower = y;
else
upper = y;
}
}
void solve111(int *ii, int n, long long *xx_, long long *yy_, long long *ss_) {
static long long yld[N], ylu[N], yrd[N], yru[N];
int i, j;
for (i = 0; i < n; i++) {
yld[i] = min(i == 0 ? INF : yld[i - 1], yy[ii[i]]);
ylu[i] = max(i == 0 ? -INF : ylu[i - 1], yy[ii[i]]);
}
for (i = n - 1; i >= 0; i--) {
yrd[i] = min(i + 1 == n ? INF : yrd[i + 1], yy[ii[i]]);
yru[i] = max(i + 1 == n ? -INF : yru[i + 1], yy[ii[i]]);
}
for (i = 1; i < n; i++) {
long long yd, yu;
yd = INF, yu = -INF;
for (j = i; j + 1 < n; j++) {
yd = min(yd, yy[ii[j]]), yu = max(yu, yy[ii[j]]);
if (xx[ii[i - 1]] < xx[ii[i]] && xx[ii[j]] < xx[ii[j + 1]] && max(yu - yd, 1) <= xx[ii[j + 1]] - xx[ii[i - 1]] - 2) {
long long x1, y1, l1, x2, y2, l2, x3, y3, l3;
l1 = max(max(xx[ii[i - 1]] - xx[ii[0]], ylu[i - 1] - yld[i - 1]), 1);
x1 = xx[ii[i - 1]] - l1, y1 = ylu[i - 1] - l1;
l2 = max(max(xx[ii[n - 1]] - xx[ii[j + 1]], yru[j + 1] - yrd[j + 1]), 1);
x2 = xx[ii[j + 1]], y2 = yru[j + 1] - l2;
l3 = max(xx[ii[j]] - xx[ii[i]], max(yu - yd, 1));
x3 = min(xx[ii[i]], xx[ii[j + 1]] - 1 - l3), y3 = yu - l3;
if (max(max(ss_[0], ss_[1]), ss_[2]) > max(max(l1, l2), l3))
xx_[0] = x1, yy_[0] = y1, ss_[0] = l1, xx_[1] = x2, yy_[1] = y2, ss_[1] = l2, xx_[2] = x3, yy_[2] = y3, ss_[2] = l3;
}
}
}
}
int main() {
static int ii[N];
static long long xx_[3], yy_[3], ss_[3];
int k, h, i, r;
long long tmp;
scanf("%d%d", &n, &k);
for (i = 0; i < n; i++) {
scanf("%d%d", &xx[i], &yy[i]);
ii[i] = i;
}
ss_[0] = INF;
if (k == 1)
solve1(ii, n, xx_, yy_, ss_);
else if (k == 2)
for (r = 0; r < 2; r++) {
sort(ii, 0, n);
solve2(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
}
else if (k == 3) {
for (r = 0; r < 4; r++) {
sort(ii, 0, n);
solve21(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = -yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = -yy_[h], yy_[h] = tmp, xx_[h] -= ss_[h];
}
for (r = 0; r < 2; r++) {
sort(ii, 0, n);
solve111(ii, n, xx_, yy_, ss_);
for (i = 0; i < n; i++)
tmp = xx[i], xx[i] = yy[i], yy[i] = tmp;
for (h = 0; h < k; h++)
tmp = xx_[h], xx_[h] = yy_[h], yy_[h] = tmp;
}
}
for (h = 0; h < k; h++)
printf("%lld %lld %lld\n", xx_[h], yy_[h], ss_[h]);
return 0;
}
Compilation message
izvanzemaljci.c: In function 'main':
izvanzemaljci.c:169:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
169 | scanf("%d%d", &n, &k);
| ^~~~~~~~~~~~~~~~~~~~~
izvanzemaljci.c:171:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
171 | scanf("%d%d", &xx[i], &yy[i]);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
26 ms |
1424 KB |
Output is correct |
8 |
Correct |
29 ms |
1380 KB |
Output is correct |
9 |
Correct |
26 ms |
1444 KB |
Output is correct |
10 |
Correct |
24 ms |
1360 KB |
Output is correct |
11 |
Correct |
26 ms |
1356 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
0 ms |
204 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
0 ms |
204 KB |
Output is correct |
8 |
Correct |
0 ms |
204 KB |
Output is correct |
9 |
Correct |
0 ms |
204 KB |
Output is correct |
10 |
Correct |
57 ms |
3004 KB |
Output is correct |
11 |
Correct |
56 ms |
2884 KB |
Output is correct |
12 |
Correct |
57 ms |
2956 KB |
Output is correct |
13 |
Correct |
56 ms |
2980 KB |
Output is correct |
14 |
Correct |
60 ms |
3008 KB |
Output is correct |
15 |
Correct |
63 ms |
3000 KB |
Output is correct |
16 |
Correct |
56 ms |
2888 KB |
Output is correct |
17 |
Correct |
50 ms |
2780 KB |
Output is correct |
18 |
Correct |
49 ms |
2712 KB |
Output is correct |
19 |
Correct |
45 ms |
2408 KB |
Output is correct |
20 |
Correct |
47 ms |
2636 KB |
Output is correct |
21 |
Correct |
59 ms |
3108 KB |
Output is correct |
22 |
Correct |
58 ms |
2984 KB |
Output is correct |
23 |
Correct |
59 ms |
3012 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
332 KB |
Output is correct |
2 |
Correct |
0 ms |
332 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
0 ms |
332 KB |
Output is correct |
5 |
Correct |
0 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
332 KB |
Output is correct |
7 |
Correct |
0 ms |
280 KB |
Output is correct |
8 |
Correct |
0 ms |
332 KB |
Output is correct |
9 |
Correct |
0 ms |
332 KB |
Output is correct |
10 |
Correct |
0 ms |
332 KB |
Output is correct |
11 |
Correct |
0 ms |
332 KB |
Output is correct |
12 |
Correct |
0 ms |
332 KB |
Output is correct |
13 |
Correct |
0 ms |
332 KB |
Output is correct |
14 |
Correct |
0 ms |
332 KB |
Output is correct |
15 |
Correct |
0 ms |
280 KB |
Output is correct |
16 |
Correct |
0 ms |
332 KB |
Output is correct |
17 |
Correct |
0 ms |
332 KB |
Output is correct |
18 |
Correct |
0 ms |
332 KB |
Output is correct |
19 |
Correct |
0 ms |
332 KB |
Output is correct |
20 |
Correct |
0 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
0 ms |
288 KB |
Output is correct |
23 |
Correct |
0 ms |
332 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
1 ms |
332 KB |
Output is correct |
26 |
Correct |
0 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
344 KB |
Output is correct |
2 |
Correct |
5 ms |
332 KB |
Output is correct |
3 |
Correct |
6 ms |
332 KB |
Output is correct |
4 |
Correct |
5 ms |
304 KB |
Output is correct |
5 |
Correct |
6 ms |
408 KB |
Output is correct |
6 |
Correct |
6 ms |
420 KB |
Output is correct |
7 |
Correct |
5 ms |
332 KB |
Output is correct |
8 |
Correct |
5 ms |
412 KB |
Output is correct |
9 |
Correct |
6 ms |
332 KB |
Output is correct |
10 |
Correct |
6 ms |
332 KB |
Output is correct |
11 |
Correct |
6 ms |
332 KB |
Output is correct |
12 |
Correct |
6 ms |
408 KB |
Output is correct |
13 |
Correct |
6 ms |
304 KB |
Output is correct |
14 |
Correct |
5 ms |
332 KB |
Output is correct |
15 |
Correct |
5 ms |
332 KB |
Output is correct |
16 |
Correct |
4 ms |
332 KB |
Output is correct |
17 |
Correct |
5 ms |
332 KB |
Output is correct |
18 |
Correct |
5 ms |
332 KB |
Output is correct |
19 |
Correct |
4 ms |
332 KB |
Output is correct |
20 |
Correct |
5 ms |
332 KB |
Output is correct |
21 |
Correct |
6 ms |
396 KB |
Output is correct |
22 |
Correct |
6 ms |
332 KB |
Output is correct |
23 |
Correct |
6 ms |
332 KB |
Output is correct |
24 |
Correct |
5 ms |
332 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
332 KB |
Output is correct |
2 |
Correct |
6 ms |
332 KB |
Output is correct |
3 |
Correct |
6 ms |
356 KB |
Output is correct |
4 |
Correct |
6 ms |
412 KB |
Output is correct |
5 |
Correct |
6 ms |
408 KB |
Output is correct |
6 |
Correct |
6 ms |
332 KB |
Output is correct |
7 |
Correct |
6 ms |
412 KB |
Output is correct |
8 |
Correct |
5 ms |
332 KB |
Output is correct |
9 |
Correct |
5 ms |
332 KB |
Output is correct |
10 |
Correct |
5 ms |
332 KB |
Output is correct |
11 |
Correct |
5 ms |
412 KB |
Output is correct |
12 |
Correct |
6 ms |
412 KB |
Output is correct |
13 |
Correct |
5 ms |
332 KB |
Output is correct |
14 |
Execution timed out |
3093 ms |
5476 KB |
Time limit exceeded |
15 |
Halted |
0 ms |
0 KB |
- |