fork download
copy 
  1. # include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define pii pair<int, int>
  6. #define pll pair<ll, ll>
  7.  
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define mp make_pair
  11.  
  12. #define fi first
  13. #define se second
  14. #define y0 asdsahhajkshdasdks
  15. #define y1 asdjklasjldkjklqwj
  16. #define next asdjlsadjlwjerwj
  17. #define prev sdjfkljlkwjrweur
  18.  
  19. typedef long long ll;
  20. typedef long double ld;
  21. typedef unsigned long long ull;
  22.  
  23. const ll inf = (ll)1e9 + 7;
  24. const ll maxn = (ll)2e5 + 7;
  25. const ll lmaxn = (ll)6e6 + 7;
  26. const ll linf = (ll)1e15 + 7;
  27.  
  28. const ld eps = ld(1e-11);
  29.  
  30. const ll dx[] = {-1, 0, 0, 1};
  31. const ll dy[] = {0, -1, 1, 0};
  32.  
  33. ll gcd(ll a, ll b){
  34.     while(b) a %= b, swap(a, b);
  35.     return a | b;
  36. }
  37.  
  38. ll lcm(ll a, ll b){
  39.     return a * b / gcd(a, b);
  40. }
  41.  
  42. ll n, x1, y1, x2, y2;
  43. ll x[maxn], y[maxn];
  44. map < ll, set < ll > > xx, yy;
  45. map < pll, ll > d;
  46.  
  47. int main(){
  48.     freopen("lasers.in", "r", stdin);
  49.     freopen("lasers.out", "w", stdout);
  50.     scanf("%lld %lld %lld %lld %lld", &n, &x1, &y1, &x2, &y2);
  51.     for(ll i = 1; i <= n; ++i){
  52.         scanf("%lld %lld", &x[i], &y[i]);
  53.         xx[x[i]].insert(y[i]);
  54.         yy[y[i]].insert(x[i]);
  55.     }
  56.     xx[x2].insert(y2);
  57.     yy[y2].insert(x2);
  58.     queue < pll > q;
  59.     q.push(mp(x1, y1));
  60.     while(!q.empty()){
  61.         pll v = q.front();
  62.         q.pop();
  63.         vector < ll > xt, yt;
  64.         for(ll i : xx[v.fi])
  65.             if(!d.count(mp(v.fi, i)))
  66.                 d[mp(v.fi, i)] = d[v] + 1, q.push(mp(v.fi, i)), xt.pb(i);
  67.         for(ll i : yy[v.se])
  68.             if(!d.count(mp(i, v.se)))
  69.                 d[mp(i, v.se)] = d[v] + 1, q.push(mp(i, v.se)), yt.pb(i);
  70.         for(ll i : xt) xx[v.fi].erase(i);
  71.         for(ll i : yt) yy[v.se].erase(i);
  72.     }
  73.     if(!d.count(mp(x2, y2)))
  74.         printf("-1");
  75.     else
  76.         printf("%lld", d[mp(x2, y2)] - 1);
  77.     return 0;
  78. }
  79.  
Success #stdin #stdout 0s 6600KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/WyElvG
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
public

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!