#include <bits/stdc++.h>
using namespace std;
const int INF=2e9;
int n,k,c[200001][4],mn=INF,mx,mn2=INF,mx2,x,y,mask[200001];
vector <pair <int, int>> res;
vector <int> v,ve[16];
vector <pair <int, int>> type[16];
bool check(vector <int> v, int k){
if (v.empty()){
while (k--)
cout << 1 << ' ' << 1 << '\n';
return true;
}
if (!k)
return false;
int a[2]={INF,0},b[2]={INF,0};
for (int i:v){
a[0]=min(a[0],c[i][2]);
a[1]=max(a[1],c[i][0]);
b[0]=min(b[0],c[i][3]);
b[1]=max(b[1],c[i][1]);
}
for (int i=0;i<2;i++)
for (int j=0;j<2;j++){
vector <int> v2;
for (int k:v)
if (c[k][0]>a[i]||c[k][2]<a[i]||c[k][1]>b[j]||c[k][3]<b[j])
v2.push_back(k);
if (check(v2,k-1)){
cout << a[i] << ' ' << b[j] << '\n';
return true;
}
}
return false;
}
void strain(int idx, int a, int b, int sign){
x=a,y=b;
sort(ve[idx].begin(),ve[idx].end(),[](int i, int j){
return make_pair(c[i][x],c[i][y])<make_pair(c[j][x],c[j][y]);
});
int mx=-INF;
for (int i:ve[idx]){
while (!type[idx].empty()&&c[i][y]*sign>type[idx].back().second*sign)
type[idx].pop_back();
type[idx].push_back({c[i][x],c[i][y]});
}
}
int f(int mask, int pos, int pos2=-INF){
int res=(type[mask].empty()?INF:type[mask][0].second);
if (!type[6].empty()){
int tmp=upper_bound(type[6].begin(),type[6].end(),make_pair(pos2,INF))-type[6].begin();
if (tmp<type[6].size())
res=min(res,type[6][tmp].second);
}
if (!type[mask|1].empty()){
if (mask==4){
int tmp=lower_bound(type[5].begin(),type[5].end(),make_pair(pos,0))-type[5].begin()-1;
if (tmp>=0)
res=min(res,type[5][tmp].second);
}
if (mask==2){
int tmp=upper_bound(type[3].begin(),type[3].end(),make_pair(pos,0))-type[3].begin();
if (tmp<type[3].size())
res=min(res,type[3][tmp].second);
}
}
return res;
}
pair <int, int> calc(int x, int y){
int l=0,r=INF;
if (!type[12].empty()){
int tmp=upper_bound(type[12].begin(),type[12].end(),make_pair(x,INF))-type[12].begin();
if (tmp<type[12].size())
r=type[12][tmp].second;
}
if (!type[10].empty()){
int tmp=upper_bound(type[10].begin(),type[10].end(),make_pair(y,INF))-type[10].begin();
if (tmp<type[10].size())
l=type[10][tmp].second;
}
return {l,r};
}
int main(){
ios_base::sync_with_stdio(NULL);cin.tie(nullptr);
freopen("HamburgSteak.inp","r",stdin);
cin >> n >> k;
for (int i=0;i<n;i++){
for (int j=0;j<4;j++)
cin >> c[i][j];
v.push_back(i);
}
if (check(v,k))
return 0;
for (int i=0;i<n;i++){
mn=min(mn,c[i][2]);
mx=max(mx,c[i][0]);
mn2=min(mn2,c[i][3]);
mx2=max(mx2,c[i][1]);
}
for (int i=0;i<n;i++){
mask[i]=(c[i][0]<=mn)+(c[i][3]>=mx2)*2+(c[i][1]<=mn2)*4+(c[i][2]>=mx)*8;
if (__builtin_popcount(mask[i])<3)
ve[mask[i]].push_back(i);
}
strain(1,1,3,1);
strain(2,0,2,1);
strain(4,0,2,1);
strain(8,1,3,1);
strain(3,1,2,1);
strain(5,3,2,-1);
strain(10,0,1,-1);
strain(12,0,3,1);
strain(9,1,3,1);
strain(6,0,2,1);
for (int i=0;i<n;i++){
int pos=c[i][1];
if (mask[i]%2==0||(!type[1].empty()&&(pos<type[1].back().first||pos>type[1][0].second)))
continue;
int l=0,r=INF;
if (!type[8].empty()){
l=type[8].back().first;
r=type[8][0].second;
}
if (!type[9].empty()){
if (pos<=type[9][0].second){
int tmp=upper_bound(type[9].begin(),type[9].end(),make_pair(pos,INF))-type[9].begin();
if (tmp<type[9].size()){
l=max(l,type[9].back().first);
r=min(r,type[9][tmp].second);
}
}
else if (pos>=type[9].back().first){
int lo=0,hi=type[9].size(),kq=-1;
while (lo<=hi){
int mid=(lo+hi)>>1;
if (type[9][mid].second<pos){
r=min(r,type[9][mid].first);
kq=mid;
lo=mid+1;
}
else
hi=mid-1;
}
if (kq!=-1)
l=max(l,type[9][0].second);
}
else{
l=max(l,type[9].back().first);
r=min(r,type[9][0].second);
}
}
int pos2=f(4,pos);
if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos2)){
int pos3=f(2,pos,pos2);
if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos3)){
if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
auto [x,y]=calc(pos2,pos3);
if (max(l,x)<=min(r,y)){
cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mn2 << '\n' << pos3 << ' ' << mx2 << '\n' << mx << ' ' << max(l,x);
return 0;
}
}
}
}
pos2=f(2,pos);
if (type[2].empty()||(!type[2].empty()&&type[2].back().first<=pos2)){
int pos3=f(4,pos,pos2);
if (type[4].empty()||(!type[4].empty()&&type[4].back().first<=pos3)){
if (type[6].empty()||(!type[6].empty()&&type[6].back().first<=pos3)){
auto [x,y]=calc(pos3,pos2);
if (max(l,x)<=min(r,y)){
cout << mn << ' ' << pos << '\n' << pos2 << ' ' << mx2 << '\n' << pos3 << ' ' << mn2 << '\n' << mx << ' ' << max(l,x);
return 0;
}
}
}
}
}
}
Compilation message
hamburg.cpp: In function 'void strain(int, int, int, int)':
hamburg.cpp:41:9: warning: unused variable 'mx' [-Wunused-variable]
41 | int mx=-INF;
| ^~
hamburg.cpp: In function 'int f(int, int, int)':
hamburg.cpp:52:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
52 | if (tmp<type[6].size())
| ~~~^~~~~~~~~~~~~~~
hamburg.cpp:63:20: 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 | if (tmp<type[3].size())
| ~~~^~~~~~~~~~~~~~~
hamburg.cpp: In function 'std::pair<int, int> calc(int, int)':
hamburg.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
73 | if (tmp<type[12].size())
| ~~~^~~~~~~~~~~~~~~~
hamburg.cpp:78:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
78 | if (tmp<type[10].size())
| ~~~^~~~~~~~~~~~~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:127:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
127 | if (tmp<type[9].size()){
| ~~~^~~~~~~~~~~~~~~
hamburg.cpp:85:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
85 | freopen("HamburgSteak.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 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 |
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 |
1 ms |
344 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 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 |
Incorrect |
2 ms |
348 KB |
Unexpected end of file - int32 expected |
| 2 |
Halted |
0 ms |
0 KB |
- |
