#include <bits/stdc++.h>
using namespace std;
int n,k;
int arr[200005][4];
vector<pair<int,int> > ans;
bool sc(int nk){
if(nk==0){
for(int i=0; i<n; i++) if(arr[i][0]!=-1) return false;
return true;
}
int hm[4]={-1,-1,(int)1e9,(int)1e9};
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
for(int j=0; j<2; j++){
hm[j]=max(hm[j],arr[i][j]);
}
for(int j=2; j<4; j++){
hm[j]=min(hm[j],arr[i][j]);
}
}
pair<int,int> pt;
vector<pair<int,int> > undo;
pt={hm[0],hm[1]};
ans.push_back(pt);
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
undo.push_back({i,arr[i][0]});
arr[i][0]=-1;
}
}
if(sc(nk-1)) return true;
ans.pop_back();
for(auto i:undo) arr[i.first][0]=i.second;
undo.clear();
pt={hm[2],hm[1]};
ans.push_back(pt);
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
undo.push_back({i,arr[i][0]});
arr[i][0]=-1;
}
}
if(sc(nk-1)) return true;
ans.pop_back();
for(auto i:undo) arr[i.first][0]=i.second;
undo.clear();
pt={hm[2],hm[3]};
ans.push_back(pt);
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
undo.push_back({i,arr[i][0]});
arr[i][0]=-1;
}
}
if(sc(nk-1)) return true;
ans.pop_back();
for(auto i:undo) arr[i.first][0]=i.second;
undo.clear();
pt={hm[0],hm[3]};
ans.push_back(pt);
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
undo.push_back({i,arr[i][0]});
arr[i][0]=-1;
}
}
if(sc(nk-1)) return true;
ans.pop_back();
for(auto i:undo) arr[i.first][0]=i.second;
undo.clear();
return false;
}
bool delpt(pair<int,int> pt){
vector<pair<int,int> > undo;
ans.push_back(pt);
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
if(arr[i][0]<=pt.first&&pt.first<=arr[i][2]&&arr[i][1]<=pt.second&&pt.second<=arr[i][3]){
undo.push_back({i,arr[i][0]});
arr[i][0]=-1;
}
}
if(sc(3)) return true;
ans.pop_back();
for(auto i:undo) arr[i.first][0]=i.second;
undo.clear();
return false;
}
void s4(){
int hm[4]={-1,-1,(int)1e9,(int)1e9};
for(int i=0; i<n; i++){
if(arr[i][0]==-1) continue;
for(int j=0; j<2; j++){
hm[j]=max(hm[j],arr[i][j]);
}
for(int j=2; j<4; j++){
hm[j]=min(hm[j],arr[i][j]);
}
}
for(int i=0; i<n; i++){
int bru[4];
for(int j=0; j<4; j++) bru[j]=hm[j];
for(int j=0; j<2; j++){
bru[j]=max(bru[j],arr[i][j]);
}
for(int j=2; j<4; j++){
bru[j]=min(bru[j],arr[i][j]);
}
pair<int,int> pt={bru[0],bru[1]};
if(delpt(pt)) return;
pt={bru[0],bru[3]};
if(delpt(pt)) return;
pt={bru[2],bru[3]};
if(delpt(pt)) return;
pt={bru[2],bru[1]};
if(delpt(pt)) return;
}
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i=0; i<n; i++) for(int j=0; j<4; j++) cin >> arr[i][j];
if(sc(k)){
for(auto i:ans) cout << i.first << ' ' << i.second << '\n';
}
else{
ans.clear();
s4();
for(auto i:ans) cout << i.first << ' ' << i.second << '\n';
}
}
# | 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... |