This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<tuple>
#include<algorithm>
#define ep emplace
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const int inf=1e9+7;
const ll INF=1e18;
inline bool check(const pair<pi,pi>&sq,const pi&p)
{
return sq.fi.fi<=p.fi&&p.fi<=sq.fi.se&&sq.se.fi<=p.se&&p.se<=sq.se.se;
}
inline pi get1(const vector<pair<pi,pi> >&v)
{
int xmx=-inf,ymx=-inf;
for(auto&t:v)
xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi);
return pi(xmx,ymx);
}
inline pair<pi,pi>get2(const vector<pair<pi,pi> >&v)
{
int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
for(auto&t:v)
xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
pi p[4]={pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymn),pi(xmn,ymx)};
for(int i=0;i<2;i++)
{
int j=i+2;
bool f=1;
for(auto&t:v)
{
if(!check(t,p[i])&&!check(t,p[j]))
{
f=0;
break;
}
}
if(f)
return pair<pi,pi>(p[i],p[j]);
}
return pair<pi,pi>(pi(-1,-1),pi(-1,-1));
}
tuple<pi,pi,pi>get3(const vector<pair<pi,pi> >&v)
{
int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
for(auto&t:v)
xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
vector<pi>pv({pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymx),pi(xmn,ymn)});
for(pi&p:pv)
{
vector<pair<pi,pi> >nxv;
for(auto&t:v)
if(!check(t,p))
nxv.eb(t);
auto cget=get2(nxv);
if(cget.fi.fi!=-1)
return tuple<pi,pi,pi>(p,cget.fi,cget.se);
}
return tuple<pi,pi,pi>(pi(-1,-1),pi(-1,-1),pi(-1,-1));
}
tuple<pi,pi,pi,pi>get4(const vector<pair<pi,pi> >&v)
{
int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
for(auto&t:v)
xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
vector<pi>pv({pi(xmx,ymx),pi(xmx,ymn),pi(xmn,ymx),pi(xmn,ymn)});
for(pi&p:pv)
{
vector<pair<pi,pi> >nxv;
for(auto&t:v)
if(!check(t,p))
nxv.eb(t);
auto cget=get3(nxv);
if(get<0>(cget).fi!=-1)
return tuple<pi,pi,pi,pi>(p,get<0>(cget),get<1>(cget),get<2>(cget));
}
return tuple<pi,pi,pi,pi>(pi(-1,-1),pi(-1,-1),pi(-1,-1),pi(-1,-1));
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n,k;
cin>>n>>k;
vector<pair<pi,pi> >v(n);
for(auto&t:v)
cin>>t.fi.fi>>t.se.fi>>t.fi.se>>t.se.se;
if(k==1)
{
pi ans=get1(v);
cout<<ans.fi<<' '<<ans.se<<endl;
return 0;
}
if(k==2)
{
auto ans=get2(v);
cout<<ans.fi.fi<<' '<<ans.fi.se<<' '<<ans.se.fi<<' '<<ans.se.se<<endl;
return 0;
}
if(k==3)
{
auto ans=get3(v);
cout<<get<0>(ans).fi<<' '<<get<0>(ans).se<<endl;
cout<<get<1>(ans).fi<<' '<<get<1>(ans).se<<endl;
cout<<get<2>(ans).fi<<' '<<get<2>(ans).se<<endl;
return 0;
}
{
auto ans=get4(v);
if(get<0>(ans).fi!=-1)
{
cout<<get<0>(ans).fi<<' '<<get<0>(ans).se<<endl;
cout<<get<1>(ans).fi<<' '<<get<1>(ans).se<<endl;
cout<<get<2>(ans).fi<<' '<<get<2>(ans).se<<endl;
cout<<get<3>(ans).fi<<' '<<get<3>(ans).se<<endl;
return 0;
}
}
int xmx=-inf,xmn=inf,ymx=-inf,ymn=inf;
for(auto&t:v)
xmx=max(xmx,t.fi.fi),ymx=max(ymx,t.se.fi),
xmn=min(xmn,t.fi.se),ymn=min(ymn,t.se.se);
for(auto&t:v)
{
if(t.fi.fi<=xmn)
{
}
else if(t.se.fi<=ymn)
{
}
else if(t.se.se>=ymx)
{
}
else
{
}
}
return 0;
}
# | 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... |