fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. const int N = 1e5+10, M = 3e3+2, OO = 0x3f3f3f3f;
  5. int t, n, u, v, c,q;
  6. int vis[N];
  7. vector<int>vi;
  8. int bs(int x,vector<int>v){
  9.     int low=0,high=v.size()-1,med;
  10.     while(low<high){
  11.         med=(low+high+1)/2;
  12.         if(v[med]<=x) low=med;
  13.         else high=med-1;
  14.  
  15.     }
  16.     return v[low];
  17. }
  18. int main(){
  19.     cin>>t;
  20.     while(t--){
  21.     	int maxi=0;
  22.         vector<int>v;
  23.         cin>>n>>q;
  24.         for(int i=0;i<n;++i){
  25.             int x,y; cin>>x>>y;
  26.             v.push_back(x);
  27.             //mp[{x,y}]=1;
  28.             maxi=max(maxi,x);
  29.         }
  30.  
  31.         sort(v.begin(),v.end());
  32.         while(q--){
  33.         	int x,y,nx,ny; cin>>x>>y>>nx>>ny;
  34.         	if(n==0){
  35.         		cout<<abs(nx-x) <<"\n";
  36.         		continue;
  37.         	}
  38.             ll ans=0;
  39.  
  40.             int dis1=abs((*lower_bound(v.begin(),v.end(),x)));
  41.             int dis2=abs(bs(x,v)-x);
  42.            // cout<<dis2<<" ";
  43.             ans+=min(dis1,dis2);
  44.             //cout<<ans;
  45.             dis1=abs((*lower_bound(v.begin(),v.end(),nx))-nx);
  46.             //cout<<dis1<<" ";
  47.             dis2=abs(bs(nx,v)-nx);
  48.             //cout<<dis2;
  49.             ans+=min(dis1,dis2);
  50.             cout<<min((ll)abs(nx-x),ans)<<"\n";
  51.         }
  52.  
  53.     }
  54.  
  55. }
Success #stdin #stdout 0s 15624KB
comments (?)
stdin
copy 
1
2 1
3 1
1 1
3 1 10 1
stdout
copy 
7
https://ideone.com/P1TT3z
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!