#include <bits/stdc++.h>
using namespace std;
using ii = pair<int, int>;
#define X first
#define Y second
const int inf = int(1e9) + 7;
struct rect {
int l, r, d, u;
rect() {
}
rect(int l, int r, int d, int u) {
this->l = l;
this->r = r;
this->d = d;
this->u = u;
}
};
bool rects_intersect(rect &a, rect &b) {
return max(a.l, b.l) <= min(a.r, b.r) && max(a.d, b.d) <= min(a.u, b.u);
}
void normalise(vector<ii> &V, int dx, int dy) {
if(dx == 1)
sort(V.begin(), V.end());
else
sort(V.begin(), V.end(), greater<ii>());
vector<ii> res;
for(auto r : V) {
while(!res.empty() && res.back().Y * dy >= r.Y * dy)
res.pop_back();
if(res.empty() || res.back().X * dx < r.X * dx)
res.push_back(r);
}
V = res;
}
void add_candidates(vector<int> &cand, vector<ii> &P) {
for(auto p : P)
cand.push_back(p.X);
}
vector<ii> solve_one_side(vector<rect> &V) {
int L = 0, R = inf, D = 0, U = inf;
for(auto r : V) {
L = max(L, r.l);
R = min(R, r.r);
D = max(D, r.d);
U = min(U, r.u);
}
if(L > R)
swap(L, R);
if(D > U)
swap(D, U);
//~ cout << L << " " << R << " " << D << " "<< U << endl;
vector<ii> LU, LD, RU, RD, DU, LR;
int minU = L, maxU = R, minD = L, maxD = R, minL = D, maxL = U, minR = D, maxR = U;
rect rL(L, L, D, U), rR(R, R, D, U), rD(L, R, D, D), rU(L, R, U, U);
for(auto r : V) {
int mask = 0;
if(rects_intersect(rL, r)) mask |= 1;
if(rects_intersect(rR, r)) mask |= 2;
if(rects_intersect(rD, r)) mask |= 4;
if(rects_intersect(rU, r)) mask |= 8;
if(__builtin_popcount(mask) >= 3)
continue;
if(mask == 1) {
minL = max(minL, r.d);
maxL = min(maxL, r.u);
} else if(mask == 2) {
minR = max(minR, r.d);
maxR = min(maxR, r.u);
} else if(mask == 4) {
minD = max(minD, r.l);
maxD = min(maxD, r.r);
} else if(mask == 8) {
minU = max(minU, r.l);
maxU = min(maxU, r.r);
} else if(mask == 3) {
LR.emplace_back(r.d, r.u);
} else if(mask == 12) {
DU.emplace_back(r.l, r.r);
} else if(mask == 9) {
LU.emplace_back(r.d, r.r);
} else if(mask == 5) {
LD.emplace_back(r.u, r.r);
} else if(mask == 10) {
RU.emplace_back(r.d, r.l);
} else if(mask == 6) {
RD.emplace_back(r.u, r.l);
} else
exit(5);
}
normalise(LR, 1, 1);
normalise(DU, 1, 1);
normalise(LU, 1, 1);
normalise(LD, -1, 1);
normalise(RU, 1, -1);
normalise(RD, -1, -1);
vector<int> candL;
add_candidates(candL, LR);
add_candidates(candL, LU);
add_candidates(candL, LD);
candL.push_back(D);
sort(candL.begin(), candL.end());
candL.resize(distance(candL.begin(), unique(candL.begin(), candL.end())));
int lstLR = -1, lstLD = LD.size() - 1, lstLU = -1, lstDU = DU.size() - 1;
for(int ly : candL) {
//~ cout << "cand " << ly << endl;
if(ly < minL || ly > maxL)
continue;
while(lstLR + 1 < LR.size() && LR[lstLR + 1].X <= ly && ly <= LR[lstLR + 1].Y)
lstLR++;
while(lstLD >= 0 && LD[lstLD].X < ly)
lstLD--;
while(lstLU + 1 < LU.size() && LU[lstLU + 1].X <= ly)
lstLU++;
int d1 = minD;
int d2 = min({maxD, lstLD + 1 < LD.size() ? LD[lstLD + 1].Y : inf, DU.size() ? DU[0].Y : inf});
if(d1 > d2)
continue;
int dx = d2; //maleje!
while(lstDU >= 0 && DU[lstDU].X > dx)
lstDU--;
int u1 = max({minU, lstDU + 1 < DU.size() ? DU.back().X : 0});
int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
if(u1 > u2)
continue;
int ux = u2; // oj chyba losowo :-/
//~ cout << ly << " " << dx << " " << ux << endl;
int r1 = minR;
int r2 = maxR;
for(auto r : LR)
if(r.Y < ly || r.X > ly)
r1 = max(r1, r.X), r2 = min(r2, r.Y);
for(auto r : RD)
if(r.X > dx)
r2 = min(r2, r.Y);
for(auto r : RU)
if(r.X > ux)
r1 = max(r1, r.Y);
if(r1 > r2)
continue;
int ry = r2; // uff
return {{L, ly}, {dx, D}, {R, ry}, {ux, U}};
}
return {};
}
bool check(vector<rect> &V, vector<ii> &P) {
for(auto r : V) {
bool ok = false;
for(auto p : P)
if(r.l <= p.X && p.X <= r.r && r.d <= p.Y && p.Y <= r.u)
ok = true;
if(!ok)
return false;
}
return true;
}
vector<ii> solve(vector<rect> &V, int k) {
vector<ii> r = solve_one_side(V);
if(r.empty()) {
for(auto &r : V) {
r.u = inf-r.u;
r.d = inf-r.d;
swap(r.d, r.u);
}
r = solve_one_side(V);
for(auto &rr : r) {
rr.Y = inf - rr.Y;
}
for(auto &r : V) {
r.u = inf-r.u;
r.d = inf-r.d;
swap(r.d, r.u);
}
}
for(int mask = 1 ; mask < (1 << 4) ; mask++) {
if(__builtin_popcount(mask) == k) {
vector<ii> fin;
for(int i = 0 ; i < 4 ; i++)
if((1 << i) & mask)
fin.push_back(r[i]);
if(check(V, fin))
return fin;
}
}
exit(10);
return r;
}
int main() {
int n, k;
scanf("%d%d", &n, &k);
vector<rect> R(n);
for(int i = 0 ; i < n ; i++)
scanf("%d%d%d%d", &R[i].l, &R[i].d, &R[i].r, &R[i].u);
vector<ii> res = solve(R, k);
for(auto p : res)
printf("%d %d\n", p.X, p.Y);
return 0;
}
Compilation message
hamburg.cpp: In function 'std::vector<std::pair<int, int> > solve_one_side(std::vector<rect>&)':
hamburg.cpp:134:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
134 | while(lstLR + 1 < LR.size() && LR[lstLR + 1].X <= ly && ly <= LR[lstLR + 1].Y)
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:138:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
138 | while(lstLU + 1 < LU.size() && LU[lstLU + 1].X <= ly)
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:142:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | int d2 = min({maxD, lstLD + 1 < LD.size() ? LD[lstLD + 1].Y : inf, DU.size() ? DU[0].Y : inf});
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:152:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
152 | int u1 = max({minU, lstDU + 1 < DU.size() ? DU.back().X : 0});
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:153:33: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp:153:80: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
153 | int u2 = min({maxU, lstDU + 1 < DU.size() ? DU[lstDU + 1].Y : inf, lstLU + 1 < LU.size() ? LU[lstLU + 1].Y : inf});
| ~~~~~~~~~~^~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:232:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
232 | scanf("%d%d", &n, &k);
| ~~~~~^~~~~~~~~~~~~~~~
hamburg.cpp:236:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
236 | scanf("%d%d%d%d", &R[i].l, &R[i].d, &R[i].r, &R[i].u);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
147 ms |
3448 KB |
Output is correct |
| 6 |
Correct |
145 ms |
3448 KB |
Output is correct |
| 7 |
Correct |
156 ms |
3448 KB |
Output is correct |
| 8 |
Correct |
220 ms |
3424 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
384 KB |
Output is correct |
| 3 |
Correct |
3 ms |
384 KB |
Output is correct |
| 4 |
Correct |
3 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
2 ms |
384 KB |
Output is correct |
| 7 |
Runtime error |
2 ms |
384 KB |
Execution failed because the return code was nonzero |
| 8 |
Halted |
0 ms |
0 KB |
- |
