#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
#define int ll
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const ll NMAX = 400005;
const ll INF = 1e9;
const ll nrbits = 20;
const ll MOD = 998244353;
struct rect {
int x1, y1, x2, y2;
} v[NMAX];
int n, k;
vector <pii> sol;
int taken[NMAX];
rect intersect(rect a, rect b) {
rect sol = {max(a.x1, b.x1), max(a.y1, b.y1), min(a.x2, b.x2), min(a.y2, b.y2)};
return sol;
}
bool isIn(pii a, rect r) {
return (r.x1 <= a.first && a.first <= r.x2 && r.y1 <= a.second && a.second <= r.y2);
}
rect solve1() {
int i;
rect sol = {0, 0, INF, INF};
for(i = 1; i <= n; i++) {
sol = intersect(sol, v[i]);
}
return sol;
}
void afiseaza() {
for(auto x : sol) {
cout << x.first << " " << x.second << "\n";
}
k -= sol.size();
while(k--) {
cout << "0 0\n";
}
exit(0);
}
void tryy(int lvl) {
int i;
if(lvl == 0) {
int ok = 1;
for(i = 1; i <= n; i++) {
ok &= (taken[i] > 0);
}
if(ok) {
afiseaza();
}
return;
}
int xmin = INF, xmax = 0, ymin = INF, ymax = 0;
for(i = 1; i <= n; i++) {
if(taken[i]) continue;
xmin = min(xmin, v[i].x2);
xmax = max(xmax, v[i].x1);
ymin = min(ymin, v[i].y2);
ymax = max(ymax, v[i].y1);
}
vector <pii> per;
per.push_back({xmin, ymin});
per.push_back({xmin, ymax});
per.push_back({xmax, ymin});
per.push_back({xmax, ymax});
for(int d = 0; d < 4; d++) {
pii acum = per[d];
for(i = 1; i <= n; i++) {
if(isIn(acum, v[i])) {
taken[i]++;
}
}
sol.push_back(acum);
tryy(lvl - 1);
for(i = 1; i <= n; i++) {
if(isIn(acum, v[i])) taken[i]--;
}
sol.pop_back();
}
}
vector <int> nrmX;
vector <int> nrmY;
int codedX[NMAX];
int codedY[NMAX];
unordered_map <int, int> mpX;
unordered_map <int, int> mpY;
vector <int> ev1[NMAX];
vector <int> ev2[NMAX];
vector <int> ev3[NMAX];
vector <int> ev4[NMAX];
int sum1[NMAX];
int sum2[NMAX];
int sum3[NMAX];
int sum4[NMAX];
int ini1[NMAX];
int ini2[NMAX];
int ini3[NMAX];
int ini4[NMAX];
int f[NMAX];
int x1, x2, y11, y2;
struct ura {
int unu, doi, trei, patru;
} plec[NMAX];
void add(int x, int val) {
if(plec[x].unu != -1) {
sum1[plec[x].unu] += val;
}
if(plec[x].doi != -1) {
sum2[plec[x].doi] += val;
}
if(plec[x].trei != -1) {
sum3[plec[x].trei] += val;
}
if(plec[x].patru != -1) {
sum4[plec[x].patru] += val;
}
}
int total;
pii unu, doi, trei, patru;
void reinitializeaza(){
int i;
unu = {x1, y11};
doi = {x2, y11};
trei = {x2, y2};
patru = {x1, y2};
total = 0;
for(i = 1; i < NMAX; i++){
sum1[i] = ini1[i];
sum2[i] = ini2[i];
sum3[i] = ini3[i];
sum4[i] = ini4[i];
f[i] = 0;
}
for(i = 1; i <= n; i++) {
int x = i;
if(isIn(unu, v[i])) {
f[x]++;
if(f[x] == 1) total++;
}
if(isIn(doi, v[i])) {
f[x]++;
if(f[x] == 1) total++;
}
if(isIn(trei, v[i])) {
f[x]++;
if(f[x] == 1) total++;
}
if(isIn(patru, v[i])) {
f[x]++;
if(f[x] == 1) total++;
}
}
}
signed main() {
#ifdef HOME
ifstream cin(".in");
ofstream cout(".out");
#endif // HOME
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int i;
cin >> n >> k;
for(i = 1; i <= n; i++) {
cin >> v[i].x1 >> v[i].y1 >> v[i].x2 >> v[i].y2; /// it doesn't matter
}
/// K = 1?
tryy(1);
/// K = 2?
tryy(2);
/// K = 3?
tryy(3);
/// K = 4 and pair found
tryy(4);
for(i = 1; i <= n; i++) {
nrmX.push_back(v[i].x1);
nrmX.push_back(v[i].x2);
nrmY.push_back(v[i].y2);
nrmY.push_back(v[i].y1);
}
sort(nrmX.begin(), nrmX.end());
sort(nrmY.begin(), nrmY.end());
int cnt = 0;
int lst = -1;
for(auto x : nrmX) {
if(x != lst) {
cnt++;
}
mpX[x] = cnt;
codedX[cnt] = x;
lst = x;
}
cnt = 0;
lst = -1;
for(auto x : nrmY) {
if(x != lst) {
cnt++;
}
mpY[x] = cnt;
codedY[cnt] = x;
lst = x;
}
for(i = 1; i <= n; i++) {
v[i].x1 = mpX[v[i].x1];
v[i].x2 = mpX[v[i].x2];
v[i].y1 = mpY[v[i].y1];
v[i].y2 = mpY[v[i].y2];
}
x1 = INF, x2 = 0, y11 = INF, y2 = 0;
for(i = 1; i <= n; i++) {
x1 = min(x1, v[i].x2);
x2 = max(x2, v[i].x1);
y11 = min(y11, v[i].y2);
y2 = max(y2, v[i].y1);
}
unu = {x1, y11};
doi = {x2, y11};
trei = {x2, y2};
patru = {x1, y2};
total = 0;
for(i = 1; i <= n; i++) {
plec[i] = {-1, -1, -1, -1};
if(v[i].y1 <= y11 && v[i].y2 >= y11) {
int st = max(unu.first, v[i].x1);
int dr = v[i].x2 + 1;
assert(st <= dr);
if(st <= x2) {
ev1[st].push_back(i);
}
if(dr <= x2) {
ev1[dr].push_back(-i);
plec[i].unu = v[i].x2;
sum1[v[i].x2]++;
}
}
if(v[i].x1 <= doi.first && v[i].x2 >= doi.first) {
int st = max(doi.second, v[i].y1);
int dr = v[i].y2 + 1;
assert(st <= dr);
if(st <= y2) {
ev2[st].push_back(i);
}
if(dr <= y2) {
ev2[dr].push_back(-i);
plec[i].doi = v[i].y2;
sum2[v[i].y2]++;
}
}
if(v[i].y1 <= trei.second && v[i].y2 >= trei.second) {
int st = min(trei.first, v[i].x2);
int dr = v[i].x1 - 1;
assert(st >= dr);
if(st >= x1) {
ev3[st].push_back(i);
}
if(dr >= x1) {
ev3[dr].push_back(-i);
plec[i].trei = v[i].x1;
sum3[v[i].x1]++;
}
}
if(v[i].x1 <= patru.first && v[i].x2 >= patru.first) {
int st = min(patru.second, v[i].y2);
int dr = v[i].y1 - 1;
assert(st >= dr);
if(st >= y11) {
ev4[st].push_back(i);
}
if(dr >= y11) {
ev4[dr].push_back(-i);
plec[i].patru = v[i].y1;
sum4[v[i].y1]++;
}
}
}
for(i = 1; i <= n; i++) {
int x = i;
if(isIn(unu, v[i])) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
}
if(isIn(doi, v[i])) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
}
if(isIn(trei, v[i])) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
}
if(isIn(patru, v[i])) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
}
}
for(i = 1; i <= n; i++){
ini1[i] = sum1[i], ini2[i] = sum2[i], ini3[i] = sum3[i], ini4[i] = sum4[i];
}
while(unu.first <= x2) {
if(unu.first != x1) {
for(auto x : ev1[unu.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(doi.second < y2 && sum2[doi.second] == 0) {
doi.second++;
for(auto x : ev2[doi.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(trei.first > x1 && sum3[trei.first] == 0) {
trei.first--;
for(auto x : ev3[trei.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(patru.second > y11 && sum4[patru.second] == 0) {
patru.second--;
for(auto x : ev4[patru.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
if(total == n) {
cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
return 0;
}
unu.first++;
}
reinitializeaza();
int acum = patru.second;
while(patru.second >= y11) {
if(patru.second != acum) {
for(auto x : ev4[patru.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(unu.first < x2 && sum1[unu.first] == 0) {
unu.first++;
for(auto x : ev1[unu.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(doi.second < y2 && sum2[doi.second] == 0) {
doi.second++;
for(auto x : ev2[doi.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(trei.first > x1 && sum3[trei.first] == 0) {
trei.first--;
for(auto x : ev3[trei.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
if(total == n) {
cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
return 0;
}
patru.second--;
}
reinitializeaza();
acum = trei.first;
while(trei.first >= x1) {
if(trei.first != acum) {
for(auto x : ev3[trei.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(patru.second > y11 && sum4[patru.second] == 0) {
patru.second--;
for(auto x : ev4[patru.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(unu.first < x2 && sum1[unu.first] == 0) {
unu.first++;
for(auto x : ev1[unu.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(doi.second < y2 && sum2[doi.second] == 0) {
doi.second++;
for(auto x : ev2[doi.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
if(total == n) {
cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
return 0;
}
trei.first--;
}
reinitializeaza();
acum = doi.second;
while(doi.second <= y2) {
debug(total);
if(doi.second != acum) {
for(auto x : ev2[doi.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(trei.first > x1 && sum3[trei.first] == 0) {
trei.first--;
for(auto x : ev3[trei.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(patru.second > y11 && sum4[patru.second] == 0) {
patru.second--;
for(auto x : ev4[patru.second]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
while(unu.first < x2 && sum1[unu.first] == 0) {
unu.first++;
for(auto x : ev1[unu.first]) {
if(x > 0) {
f[x]++;
if(f[x] == 1) total++;
if(f[x] == 2) {
add(x, -1);
}
} else {
f[-x]--;
if(f[-x] == 0) total--;
if(f[-x] == 1) {
add(-x, 1);
}
}
}
}
if(total == n) {
cout << codedX[unu.first] << " " << codedY[unu.second] << "\n";
cout << codedX[doi.first] << " " << codedY[doi.second] << "\n";
cout << codedX[trei.first] << " " << codedY[trei.second] << "\n";
cout << codedX[patru.first] << " " << codedY[patru.second] << "\n";
return 0;
}
doi.second++;
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45804 KB |
Output is correct |
| 2 |
Correct |
13 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
11 ms |
45508 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45400 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
13 ms |
45532 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45656 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
10 ms |
45400 KB |
Output is correct |
| 3 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 5 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 6 |
Correct |
11 ms |
45532 KB |
Output is correct |
| 7 |
Correct |
14 ms |
45740 KB |
Output is correct |
| 8 |
Correct |
10 ms |
45524 KB |
Output is correct |
| 9 |
Correct |
11 ms |
45400 KB |
Output is correct |
| 10 |
Correct |
12 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
10 ms |
45404 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45568 KB |
Output is correct |
| 2 |
Correct |
11 ms |
45612 KB |
Output is correct |
| 3 |
Correct |
12 ms |
45400 KB |
Output is correct |
| 4 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 5 |
Correct |
11 ms |
45560 KB |
Output is correct |
| 6 |
Correct |
11 ms |
45400 KB |
Output is correct |
| 7 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
12 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
13 ms |
45400 KB |
Output is correct |
| 10 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 13 |
Correct |
13 ms |
45508 KB |
Output is correct |
| 14 |
Incorrect |
39 ms |
70740 KB |
Unexpected end of file - int32 expected |
| 15 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
23 ms |
45804 KB |
Output is correct |
| 2 |
Correct |
13 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
11 ms |
45508 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45400 KB |
Output is correct |
| 5 |
Correct |
71 ms |
51736 KB |
Output is correct |
| 6 |
Correct |
72 ms |
51540 KB |
Output is correct |
| 7 |
Correct |
68 ms |
51740 KB |
Output is correct |
| 8 |
Correct |
69 ms |
51540 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 3 |
Correct |
13 ms |
45532 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45656 KB |
Output is correct |
| 5 |
Correct |
81 ms |
51740 KB |
Output is correct |
| 6 |
Correct |
75 ms |
51740 KB |
Output is correct |
| 7 |
Correct |
91 ms |
51540 KB |
Output is correct |
| 8 |
Correct |
75 ms |
51492 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 2 |
Correct |
10 ms |
45400 KB |
Output is correct |
| 3 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 4 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 5 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 6 |
Correct |
11 ms |
45532 KB |
Output is correct |
| 7 |
Correct |
14 ms |
45740 KB |
Output is correct |
| 8 |
Correct |
10 ms |
45524 KB |
Output is correct |
| 9 |
Correct |
11 ms |
45400 KB |
Output is correct |
| 10 |
Correct |
12 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
10 ms |
45404 KB |
Output is correct |
| 13 |
Correct |
89 ms |
51744 KB |
Output is correct |
| 14 |
Correct |
89 ms |
51764 KB |
Output is correct |
| 15 |
Correct |
90 ms |
51540 KB |
Output is correct |
| 16 |
Correct |
87 ms |
51540 KB |
Output is correct |
| 17 |
Correct |
90 ms |
51740 KB |
Output is correct |
| 18 |
Correct |
88 ms |
51744 KB |
Output is correct |
| 19 |
Correct |
104 ms |
51744 KB |
Output is correct |
| 20 |
Correct |
94 ms |
51996 KB |
Output is correct |
| 21 |
Correct |
145 ms |
51740 KB |
Output is correct |
| 22 |
Correct |
121 ms |
51740 KB |
Output is correct |
| 23 |
Correct |
103 ms |
51536 KB |
Output is correct |
| 24 |
Correct |
109 ms |
51744 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
11 ms |
45568 KB |
Output is correct |
| 2 |
Correct |
11 ms |
45612 KB |
Output is correct |
| 3 |
Correct |
12 ms |
45400 KB |
Output is correct |
| 4 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 5 |
Correct |
11 ms |
45560 KB |
Output is correct |
| 6 |
Correct |
11 ms |
45400 KB |
Output is correct |
| 7 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 8 |
Correct |
12 ms |
45404 KB |
Output is correct |
| 9 |
Correct |
13 ms |
45400 KB |
Output is correct |
| 10 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 11 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 12 |
Correct |
11 ms |
45404 KB |
Output is correct |
| 13 |
Correct |
13 ms |
45508 KB |
Output is correct |
| 14 |
Incorrect |
39 ms |
70740 KB |
Unexpected end of file - int32 expected |
| 15 |
Halted |
0 ms |
0 KB |
- |
