luanaamorim

Untitled

Aug 3rd, 2021
677
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <queue>
  3. #include <string>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <cmath>
  7. #include <iomanip>
  8. #include <map>
  9. #include <cstring>
  10. #include <set>
  11. #include <stack>
  12. #include <bitset>
  13. #define ll long long
  14. #define INF (1e9)
  15. #define MAX (int) (2e5 + 5)
  16. #define MOD 1000000007
  17. #define par pair<int, int>
  18. #define all(v) v.begin(), v.end()
  19. #define sz(x) (int) ((x).size())
  20. #define esq(x) (x<<1)
  21. #define dir(x) ((x<<1)|1)
  22. #define lsb(x) (x & -x)
  23. #define W(x) cout << #x << ": " << x << endl
  24. #define Wii(x) cout << x.first << ' ' << x.second << endl
  25. #define _ ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  26.  
  27. using namespace std;
  28.  
  29. struct tpoint
  30. {
  31.     double x, y, r;
  32. };
  33.  
  34. tpoint arr[MAX];
  35. int n, q, a, b;
  36. double dist[1000][1000];
  37.  
  38. int main()
  39. {_
  40.     while (cin >> n && n)
  41.     {
  42.         for (int i = 1; i <= n; i++)
  43.             cin >> arr[i].x >> arr[i].y >> arr[i].r;
  44.  
  45.         for (int i = 1; i <= n; i++)
  46.         {
  47.             for (int j = 1; j <= n; j++)
  48.             {
  49.                 double d = hypot(arr[i].x-arr[j].x, arr[i].y-arr[j].y);
  50.                 dist[i][j] = (arr[i].r >= d ? d : INF);
  51.             }
  52.         }
  53.  
  54.         for (int i = 1; i <= n; i++)
  55.             for (int j = 1; j <= n; j++)
  56.                 for (int k = 1; k <= n; k++)
  57.                     dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  58.         cin >> q;
  59.         while (q--)
  60.         {
  61.             cin >> a >> b;
  62.             cout << (dist[a][b] != INF ? (int) dist[a][b] : -1) << endl;
  63.         }
  64.     }
  65. }
  66.  
  67.  
  68.  
  69.  
  70.  
  71.  
  72.  
  73.  
  74.  
  75.  
  76.  
  77.  
  78.  
  79.  
  80.  
RAW Paste Data