Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long double ld;
- typedef long long ll;
- typedef pair<int,int> pii;
- const int N=1<<21;
- int T[2*N],lazy[2*N]; //T is a max seg tree
- map<int,int> compr;
- void updateR(int ql, int qr, int val, int node=1, int nl=1, int nr=N){
- if (lazy[node]!=0){
- T[node]+=lazy[node];
- if (nl!=nr){
- lazy[2*node]+=lazy[node];
- lazy[2*node+1]+=lazy[node];
- }
- lazy[node]=0;
- }
- if ((qr<nl)||(nr<ql)) return;
- if ((ql<=nl)&&(nr<=qr)){
- T[node]+=val;
- if (nl!=nr){
- lazy[2*node]+=val; lazy[2*node+1]+=val;
- }
- return;
- }
- //cout<<ql<<" "<<qr<<" "<<nl<<" "<<nr<<endl;
- int m=(nl+nr)/2;
- updateR(ql,qr,val,2*node,nl,m);
- updateR(ql,qr,val,2*node+1,m+1,nr);
- T[node]=max(T[2*node],T[2*node+1]);
- }
- int query(int ql, int qr, int node=1, int nl=1, int nr=N){
- if (lazy[node]!=0){
- T[node]+=lazy[node];
- if (nl!=nr){
- lazy[2*node]+=lazy[node];
- lazy[2*node+1]+=lazy[node];
- }
- lazy[node]=0;
- }
- if ((ql<=nl)&&(nr<=qr)) return T[node];
- if ((qr<nl)||(nr<ql)) return 0;
- int m=(nl+nr)/2;
- return max(query(ql,qr,2*node,nl,m),query(ql,qr,2*node+1,m+1,nr));
- }
- map<int,vector<pair<pii,bool>>> evs;
- int w,h;
- int conv(int x, int y){
- if (x==0) return y;
- if (y==h) return h+x;
- if (x==w) return h+w+(h-y);
- if (y==0) return h+w+h+(w-x);
- }
- int seg(ld x){
- if (x<=h) return 1;
- if (x<=h+w) return 2;
- if (x<=h+w+h) return 3;
- return 4;
- }
- pair<ld,ld> inv(ld x){
- if (x<=h) return {0,x};
- if (x<=h+w) return {x-h,h};
- if (x<=h+w+h) return {w,h-(x-h-w)};
- return {w-(x-h-w-h),0};
- }
- int main(){
- ios::sync_with_stdio(0);
- int n; cin>>n;
- cin>>w>>h;
- set<int> ys;
- ys.insert(0); ys.insert(h); ys.insert(h+w); ys.insert(h+w+h); ys.insert(h+w+h+w);
- for (int i=0;i<n;i++){
- int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;
- int p1=conv(x1,y1),p2=conv(x2,y2);
- if (p1>p2) swap(p1,p2);
- vector<int> v={0,h,h+w,h+w+h,h+w+h+w};
- v.push_back(p1); v.push_back(p2); sort(v.begin(),v.end());
- vector<pii> in,out;
- bool good=0;
- for (int i=0;i<v.size()-1;i++){
- if (good) in.push_back({v[i],v[i+1]});
- else out.push_back({v[i],v[i+1]});
- if (v[i+1]==p1) good=1;
- if (v[i+1]==p2) good=0;
- }
- ys.insert(p1); ys.insert(p2);
- for (pii p:in) for (pii q:out) if (seg(p.first+0.5)!=seg(q.first+0.5)){
- //cout<<p.first<<','<<p.second<<' '<<q.first<<','<<q.second<<endl;
- evs[p.first].push_back({q,1});
- evs[p.second].push_back({q,0});
- evs[q.first].push_back({p,1});
- evs[q.second].push_back({p,0});
- }
- }
- vector<int> yco; yco.assign(ys.begin(),ys.end());
- for (int i=0;i<yco.size();i++) compr[yco[i]]=i+1;
- for (auto asd:evs){
- for (auto e:asd.second){
- //cout<<asd.first<<": "<<e.first.first<<" "<<e.first.second<<" "<<-1+2*e.second<<endl;
- updateR(compr[e.first.first],compr[e.first.second]-1,-1+2*e.second);
- }
- if (query(1,yco.size())==n){
- for (int i=1;i<=yco.size();i++) if (query(i,i)==n){
- cout<<1<<endl;
- pair<ld,ld> a=inv(asd.first+0.5),b=inv(yco[i-1]+0.5); //push both forward by 0.5 to be in the region
- cout<<a.first<<" "<<a.second<<" "<<b.first<<" "<<b.second<<endl;
- return 0;
- }
- }
- }
- cout<<2<<endl;
- cout<<0<<" "<<0.5<<" "<<w<<" "<<h-0.5<<endl;
- cout<<0<<" "<<h-0.5<<" "<<w<<" "<<0.5<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement