Language: C++

#include<bits/stdc++.h>
using namespace std;
typedef pair<long long,long long>P;
long long w,h,m;
long long dotti=0;
vector<long long> xv,yv;
int masu[501][501]={0};
long long X1[105],X2[105],Y1[105],Y2[105];
long long dx[4]={0,1,0,-1};
long long dy[4]={1,0,-1,0};
long long check[501][501]={0};
vector<long long> node[505];
queue<P> que;
long long compress(long long *x1,long long *x2,long long w);
main(){
  cin>>w>>h>>m;
  w*=2;
  h*=2;
  for(int i=0;i<m;i++){
    cin>>X1[i]>>Y1[i]>>X2[i]>>Y2[i];
    X1[i]*=2;
    X2[i]*=2;
    Y1[i]*=2;
    Y2[i]*=2;
  }
  w=compress(X1,X2,w);
  dotti=1;
  h=compress(Y1,Y2,h);
  for(int i=0;i<m;i++){
    for(long long y=Y1[i];y<=Y2[i];y++){
      for(long long x=X1[i];x<=X2[i];x++){
	if(y<500&&x<500&&y>=0&&x>=0){
	  masu[y][x]=-1;
	}
      }
    }
  }
  long long now=0;
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      if(masu[i][j]==0){
	now++;
	que.push(P(i,j));
	while(!que.empty()){
	  int nowy=que.front().first;
	  int nowx=que.front().second;
	  que.pop();
	  masu[nowy][nowx]=now;
	  for(int k=0;k<4;k++){
	    long long nx=nowx+dx[k];
	    long long ny=nowy+dy[k];
	    if(ny>=0&&ny<h&&nx>=0&&nx<w&&masu[ny][nx]==0){
	      que.push(P(ny,nx));
	    }
	  }
	}
      }
    }
  }
  for(int i=0;i<h;i++){
    for(int j=0;j<w;j++){
      long long me=masu[i][j];
      for(int k=0;k<4;k++){
	long long ny=i+dy[k]*2;
	long long nx=j+dx[k]*2;
	if(ny>=0&&ny<h&&nx>=0&&nx<w){
	  long long to=masu[ny][nx];
	  if(me!=-1&&to!=-1&&me!=to&&check[me][to]==0){
	    node[me].push_back(to);
	    node[to].push_back(me);
	    check[me][to]=1;
	    check[to][me]=1;
	  }
	}
      }
    }
  }
  long long e;
  long long mincost[505];
  long long sx,sy,gx,gy;
  cin>>e;
  if(m==0){
    for(int i=0;i<e;i++){
      cin>>sx>>sy>>gx>>gy;
      cout<<0<<endl;
    }
  }
  else{
    for(int i=0;i<e;i++){
      long long s,g;
      cin>>sx>>sy>>gx>>gy;
      sx*=2;
      //sx++;
      sy*=2;
      //sy++;
      gx*=2;
      //gx++;
      gy*=2;
      //gy++;
      long long sxp,syp,gxp,gyp;
      sxp=max(0,upper_bound(xv.begin(),xv.end(),sx)-xv.begin()-1);
      syp=max(0,upper_bound(yv.begin(),yv.end(),sy)-yv.begin()-1);
      gxp=max(0,upper_bound(xv.begin(),xv.end(),gx)-xv.begin()-1);
      gyp=max(0,upper_bound(yv.begin(),yv.end(),gy)-yv.begin()-1);
      if(sxp>=0&&syp>=0&&gxp>=0&&gyp>=0&&sxp<w&&gxp<w&&syp<h&&gyp<h){
	s=masu[syp][sxp];
	g=masu[gyp][gxp];
	if(s==-1||g==-1) break;
	for(int j=1;j<=now;j++){
	  mincost[j]=(1LL<<60);
	}
	priority_queue<P,vector<P>,greater<P> >que;
	que.push(P(0,s));
	while(!que.empty()){
	  long long nowc=que.top().first;
	  long long nowp=que.top().second;
	  que.pop();
	  if(nowp==g){
	    cout<<nowc<<endl;
	    break;
	  }
	  for(int j=0;j<node[nowp].size();j++){
	    long long nextp=node[nowp][j];
	    if(mincost[nextp]>nowc+1){
	      mincost[nextp]=nowc+1;
	      que.push(P(nowc+1,nextp));
	    }
	  }
	}
      }
      else{
	cout<<sxp<<" "<<syp<<" "<<gxp<<" "<<gyp<<endl;
      }
    }
  }
}
long long compress(long long *x1,long long *x2,long long W){
  vector<long long> xs;
  for(int i=0;i<m;i++){
    for(long long d=-1;d<=1;d++){
      long long tx1=x1[i]+d,tx2=x2[i]+d;
      if(0<=tx1&&tx1<W) xs.push_back(tx1);
      if(0<=tx2&&tx2<W) xs.push_back(tx2);
    }
  }
  sort(xs.begin(),xs.end());
  xs.erase(unique(xs.begin(),xs.end()),xs.end());
  for(int i=0;i<m;i++){
    x1[i]=find(xs.begin(),xs.end(),x1[i])-xs.begin();
    x2[i]=find(xs.begin(),xs.end(),x2[i])-xs.begin();
  }
  if(dotti==0) xv=xs;
  else yv=xs;
  return xs.size();
}

Compiler output:
a.cc:15:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      | ^~~~
a.cc: In function 'int main()':
a.cc:101:14: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type)'
  101 |       sxp=max(0,upper_bound(xv.begin(),xv.end(),sx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/algorithm:60,
                 from /usr/include/x86_64-linux-gnu/c++/14/bits/stdc++.h:51,
                 from a.cc:1:
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:101:14: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
  101 |       sxp=max(0,upper_bound(xv.begin(),xv.end(),sx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61:
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:101:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  101 |       sxp=max(0,upper_bound(xv.begin(),xv.end(),sx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:102:14: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type)'
  102 |       syp=max(0,upper_bound(yv.begin(),yv.end(),sy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:102:14: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
  102 |       syp=max(0,upper_bound(yv.begin(),yv.end(),sy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:102:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  102 |       syp=max(0,upper_bound(yv.begin(),yv.end(),sy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:103:14: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type)'
  103 |       gxp=max(0,upper_bound(xv.begin(),xv.end(),gx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:103:14: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
  103 |       gxp=max(0,upper_bound(xv.begin(),xv.end(),gx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:103:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  103 |       gxp=max(0,upper_bound(xv.begin(),xv.end(),gx)-xv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
a.cc:104:14: error: no matching function for call to 'max(int, __gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type)'
  104 |       gyp=max(0,upper_bound(yv.begin(),yv.end(),gy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  257 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:257:5: note:   template argument deduction/substitution failed:
a.cc:104:14: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__normal_iterator<long long int*, std::vector<long long int> >::difference_type' {aka 'long int'})
  104 |       gyp=max(0,upper_bound(yv.begin(),yv.end(),gy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  303 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:303:5: note:   candidate expects 3 arguments, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5706:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(initializer_list<_Tp>)'
 5706 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5706:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5716:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(initializer_list<_Tp>, _Compare)'
 5716 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5716:5: note:   template argument deduction/substitution failed:
a.cc:104:14: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
  104 |       gyp=max(0,upper_bound(yv.begin(),yv.end(),gy)-yv.begin()-1);
      |           ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~