#include<bits/stdc++.h>
#define ll long long
const int nmax = 1e6 + 5, N = 1e6;
const ll oo = 1e9 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 1e9 + 2277, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;
int n, k;
vector<int> nen;
struct node{
int x1, y1, x2, y2;
}a[nmax];
vector<pii> ans;
void check(){
for(int i = 1; i <= n; ++i){
bool ok = 0;
for(auto [x, y] : ans){
if(a[i].x1 <= x && x <= a[i].x2 && a[i].y1 <= y && y <= a[i].y2){
ok = 1;
}
}
if(!ok) return;
}
while(ans.size() < k) ans.push_back(ans[0]);
for(auto [x, y] : ans) cout << nen[x] << ' ' << nen[y] << endl;
exit(0);
}
namespace sub1{
void sol(){
int ma = -oo, ma_2 =-oo;
for(int i = 1; i <= n; ++i){
ma = max(ma, a[i].x1);
ma_2 = max(ma_2, a[i].y1);
}
cout << nen[ma] << ' ' << nen[ma_2];
}
}
namespace sub2{
void sol(){
int y1 = oo, y2 = -oo, x1 = oo, x2 =-oo;
for(int i = 1; i <= n; ++i){
y1 = min(y1, a[i].y2);
y2 = max(y2, a[i].y1);
x1 = min(x1, a[i].x2);
x2 = max(x2, a[i].x1);
}
// check();
// cout << x1 << ' ' << y1 << ' ' << x2 << ' ' << y2 << endl;
vector<pii> tmp;
tmp.push_back({x1, y1});
tmp.push_back({x1, y2});
tmp.push_back({x2, y1});
tmp.push_back({x2, y2});
for(int i = 0; i < tmp.size(); ++i){
for(int j = i + 1; j <= tmp.size(); ++j){
ans.clear();
ans.push_back(tmp[i]);
ans.push_back(tmp[j]);
check();
}
}
}
}
namespace sub3{
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("code.inp", "r", stdin);
// freopen("code.out", "w", stdout);
cin >> n >> k;
for(int i = 1; i <= n; ++i){
cin >> a[i].x1 >> a[i].y1 >> a[i].x2 >>a[i].y2;
nen.push_back(a[i].x1);
nen.push_back(a[i].y1);
nen.push_back(a[i].x2);
nen.push_back(a[i].y2);
}
sort(nen.begin(), nen.end());
nen.erase(unique(nen.begin(), nen.end()), nen.end());
for(int i = 1; i <= n; ++i){
a[i].x1 = lower_bound(nen.begin(), nen.end(), a[i].x1) - nen.begin();
a[i].y1 = lower_bound(nen.begin(), nen.end(), a[i].y1) - nen.begin();
a[i].x2 = lower_bound(nen.begin(), nen.end(), a[i].x2) - nen.begin();
a[i].y2 = lower_bound(nen.begin(), nen.end(), a[i].y2) - nen.begin();
}
if(k == 1) return sub1::sol(),0;
if(k == 2 ||k == 3) return sub2::sol(), 0;
// sub3::sol();
}
/*
3
1 2 3 4 5 6
7 8 9 10 11
*/
Compilation message
hamburg.cpp: In function 'void check()':
hamburg.cpp:31:22: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
31 | while(ans.size() < k) ans.push_back(ans[0]);
| ~~~~~~~~~~~^~~
hamburg.cpp: In function 'void sub2::sol()':
hamburg.cpp:62:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for(int i = 0; i < tmp.size(); ++i){
| ~~^~~~~~~~~~~~
hamburg.cpp:63:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
63 | for(int j = i + 1; j <= tmp.size(); ++j){
| ~~^~~~~~~~~~~~~
hamburg.cpp: At global scope:
hamburg.cpp:76:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
76 | main(){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
556 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
3 ms |
348 KB |
Output is correct |
| 3 |
Correct |
2 ms |
556 KB |
Output is correct |
| 4 |
Correct |
2 ms |
348 KB |
Output is correct |
| 5 |
Correct |
213 ms |
7872 KB |
Output is correct |
| 6 |
Correct |
265 ms |
7872 KB |
Output is correct |
| 7 |
Correct |
249 ms |
8492 KB |
Output is correct |
| 8 |
Correct |
221 ms |
8324 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
348 KB |
Output is correct |
| 2 |
Correct |
2 ms |
604 KB |
Output is correct |
| 3 |
Correct |
2 ms |
604 KB |
Output is correct |
| 4 |
Correct |
2 ms |
604 KB |
Output is correct |
| 5 |
Correct |
276 ms |
15552 KB |
Output is correct |
| 6 |
Correct |
240 ms |
15668 KB |
Output is correct |
| 7 |
Correct |
229 ms |
15556 KB |
Output is correct |
| 8 |
Correct |
252 ms |
15640 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
