Advertisement
YEZAELP

o61_oct_c1_patshort

Dec 21st, 2021
641
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using lli = long long;
  5. const lli INF = 1e9;
  6. using pl = pair <lli, lli>;
  7. using pll = pair <pl, pl>;
  8. pll pairs[110];
  9. vector <pl> points;
  10. lli npairs, npoints;
  11.  
  12. lli Index(lli x, lli y, lli l = 0, lli r = npoints - 1){
  13.     while(l <= r){
  14.         lli mid = (l + r) / 2;
  15.         if(points[mid].first == x and points[mid].second == y) return mid;
  16.         if(points[mid].first == x){
  17.             if(points[mid].second < y) l = mid + 1;
  18.             else r = mid - 1;
  19.         }
  20.         else if(points[mid].first < x) l = mid + 1;
  21.         else r = mid - 1;
  22.     }
  23. }
  24.  
  25. lli dist(lli x1, lli y1, lli x2, lli y2){
  26.     lli dx = (lli) abs(x1 - x2);
  27.     lli dy = (lli) abs(y1 - y2);
  28.     if(dx >= dy) return dx;
  29.     return dy + (dx + dy) % 2;
  30. }
  31.  
  32. int main(){
  33.  
  34.     lli Q;
  35.     scanf("%lld %lld", &npairs, &Q);
  36.  
  37.     for(lli i=1;i<=npairs;i++){
  38.         lli x1, x2, y1, y2;
  39.         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
  40.         pairs[i] = {{x1, y1} , {x2, y2}};
  41.         points.push_back({x1, y1});
  42.         points.push_back({x2, y2});
  43.     }
  44.  
  45.     sort(points.begin(), points.end());
  46.     points.resize( unique(points.begin(), points.end()) - points.begin() );
  47.     npoints = points.size();
  48.  
  49.     // for(auto xy: points) printf("(%d,%d) ", xy.first, xy.second); cout << endl;
  50.  
  51.     lli disp[npoints][npoints];
  52.  
  53.     for(lli i=0;i<npoints;i++){
  54.         for(lli j=0;j<npoints;j++){
  55.             disp[i][j] = i == j ? 0 : dist(points[i].first, points[i].second, points[j].first, points[j].second);
  56.         }
  57.     }
  58.  
  59.     for(lli i=1;i<=npairs;i++){
  60.         lli p1 = Index(pairs[i].first.first, pairs[i].first.second);
  61.         lli p2 = Index(pairs[i].second.first, pairs[i].second.second);
  62.         disp[p1][p2] = disp[p2][p1] = 1;
  63.     }
  64.  
  65.     for(lli k=0;k<npoints;k++){
  66.         for(lli i=0;i<npoints;i++){
  67.             for(lli j=0;j<npoints;j++){
  68.                 disp[i][j] = min(disp[i][j], (lli)(disp[i][k] + disp[k][j]));
  69.             }
  70.         }
  71.     }
  72.  
  73.     for(lli q=1;q<=Q;q++){
  74.         lli x1, y1, x2, y2;
  75.         scanf("%lld %lld %lld %lld", &x1, &y1, &x2, &y2);
  76.         lli mn = dist(x1, y1, x2, y2);
  77.         for(lli i=0;i<npoints;i++){
  78.             for(lli j=0;j<npoints;j++){
  79.                 mn = min(mn, dist(x1, y1, points[i].first, points[i].second) +
  80.                              disp[i][j] +
  81.                              dist(points[j].first, points[j].second, x2, y2));
  82.             }
  83.         }
  84.         printf("%lld\n", mn);
  85.     }
  86.  
  87.     return 0;
  88. }
Advertisement
RAW Paste Data Copied
Advertisement