Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<algorithm>
- #include<iostream>
- #include<iomanip>
- #include<cstring>
- #include<cstdlib>
- #include<complex>
- #include<cstdio>
- #include<vector>
- #include<stack>
- #include<queue>
- #include<cmath>
- #include<deque>
- #include<map>
- #include<set>
- #define oo 1000000000
- #define ooll (1ll<<50)
- #define base 1000000007ll
- using namespace std;
- typedef long long ll;
- typedef pair<int,int> ii;
- typedef pair<int,ii> iii;
- typedef vector<int> vi;
- typedef vector<ii> vii;
- /* END OF TEMPLATE */
- //IOI 2014
- int R,C,n,m,ans,BIT[10000005];
- ii nans;
- vector<ii> row[1000005],col[1000005];
- vector<ii> qry[2][1000005];
- vector<int> open[2][1000005],close[2][1000005];
- void update(int x,int w) { for(; x<=C; x+=x&(-x)) BIT[x]+=w; }
- int query(int x)
- {
- int res=0;
- for(; x; x=x&(x-1)) res+=BIT[x];
- return res;
- }
- ii mn(ii u,ii v)
- {
- if(u.first==v.first) return u.second<v.second?u:v;
- return u.first<v.first?u:v;
- }
- void solve(int t)
- {
- bool fb=false;
- for(int i=1; i<=R; i++)
- {
- for(int j=0; j<open[t][i].size(); j++) update(open[t][i][j],1);
- sort(qry[!t][i].begin(),qry[!t][i].end());
- for(int j=0; j<qry[!t][i].size(); j++)
- {
- ii x=qry[!t][i][j];
- int d=query(x.second)-query(x.first-1);
- ans+=d;
- if(d && !fb)
- {
- fb=true;
- for(int k=x.first; k<=x.second; k++)
- if(query(k)!=query(k-1))
- {
- nans=mn(nans,ii(i,k));
- break;
- }
- }
- }
- for(int j=0; j<close[t][i].size(); j++) update(close[t][i][j],-1);
- }
- }
- bool dfs(int u,int v,int dir,int t)
- {
- int nu=u,nv=v,ndir;
- ii x;
- if(dir==0)
- {
- x=*(lower_bound(row[u].begin(),row[u].end(),ii(v,0))-1);
- nv=x.first;
- if(nv+1<v) qry[t][u].push_back(ii(nv+1,v-1));
- ndir=x.second?1:3;
- }
- if(dir==2)
- {
- x=*upper_bound(row[u].begin(),row[u].end(),ii(v,1));
- nv=x.first;
- if(v+1<nv) qry[t][u].push_back(ii(v+1,nv-1));
- ndir=x.second?3:1;
- }
- if(dir==1)
- {
- x=*(lower_bound(col[v].begin(),col[v].end(),ii(v,0))-1);
- nu=x.first;
- if(nu+1<u)
- {
- open[t][nu+1].push_back(v);
- close[t][u-1].push_back(v);
- }
- ndir=x.second?0:2;
- }
- if(dir==3)
- {
- x=*upper_bound(col[v].begin(),col[v].end(),ii(u,1));
- nu=x.first;
- if(u+1<nu)
- {
- open[t][u+1].push_back(v);
- close[t][nu-1].push_back(v);
- }
- ndir=x.second?2:0;
- }
- if(nu>=1 && nu<=R && nv>=1 && nv<=C) return dfs(nu,nv,ndir,t);
- return nu==R && nv==C+1;
- }
- int main()
- {
- freopen("laser.inp","r",stdin);
- freopen("laser.out","w",stdout);
- int u,v;
- scanf("%d %d %d %d",&R,&C,&n,&m);
- nans=ii(R,C);
- for(int i=1; i<=n; i++)
- {
- scanf("%d %d",&u,&v);
- row[u].push_back(ii(v,0));
- col[v].push_back(ii(u,0));
- }
- for(int i=1; i<=m; i++)
- {
- scanf("%d %d",&u,&v);
- row[u].push_back(ii(v,1));
- col[v].push_back(ii(u,1));
- }
- for(int i=1; i<=R; i++)
- {
- row[i].push_back(ii(0,0));
- row[i].push_back(ii(C+1,0));
- sort(row[i].begin(),row[i].end());
- }
- for(int i=1; i<=C; i++)
- {
- col[i].push_back(ii(0,0));
- col[i].push_back(ii(R+1,0));
- sort(col[i].begin(),col[i].end());
- }
- if(dfs(1,0,2,0))
- {
- printf("0\n");
- return 0;
- }
- dfs(R,C+1,0,1);
- solve(0);
- solve(1);
- if(ans==0) printf("Impossible\n");
- else printf("%d %d %d\n",ans,nans.first,nans.second);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement