Advertisement
deushiro

Untitled

Dec 15th, 2019
173
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.16 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <map>
  7. #include <set>
  8. #include <bitset>
  9.        
  10. using namespace std;
  11.  
  12. typedef long long ll;
  13.  
  14. struct bf{
  15.     int v, u, c;
  16. };
  17.  
  18. int main() {
  19.     int a, b, v, u, c;
  20.     cin >> a >> b;
  21.     int rx = a;
  22.     int ry = b;
  23.     v = 1e9;
  24.     u = 1e9;
  25.     map<pair<int, int>, int> m;
  26.     queue<bf> q;
  27.     vector<pair<int, int>> move = {{-1, 2}, {-1, -2}, {1, 2}, {1, -2},{2, -1}, {2, 1}, {-2, -1}, {-2, 1}};
  28.     int xx = 0;
  29.     int yy = 0;
  30.     int dist = 1e9;
  31.     while(abs(a - xx) > 10 || abs(b - yy) > 10){
  32.         for(int i = 0; i < 8; ++i){
  33.             if(sqrt(pow(a - (xx + move[i].first), 2) + pow(b - (move[i].second + yy), 2)) < sqrt(pow(a - (xx), 2) + pow(b - (yy), 2))){
  34.                 xx += move[i].first;
  35.                 dist = pow(a - (xx + move[i].first), 2) + pow(b - (move[i].second + yy), 2);
  36.                 yy += move[i].second;
  37.                 cout << xx << " " << yy << endl;
  38.                 break;
  39.             }
  40.         }
  41.     }
  42.     q.push({xx, yy, 0});
  43.     while(v != a || u != b){
  44.         v = q.front().v;
  45.         u = q.front().u;
  46.         c = q.front().c;
  47.         q.pop();
  48.         for(int i = 0; i < 8; ++i){
  49.             if(!m.count({v + move[i].first, u + move[i].second})){
  50.                 m[{v + move[i].first, u + move[i].second}] = c + 1;
  51.                 q.push({v + move[i].first, u + move[i].second, c + 1});
  52.             }
  53.         }
  54.     }
  55.     c = 1e9;
  56.     vector<pair<int, int>> ans;
  57.     while(a != 0 || b != 0){
  58.         int x = 0;
  59.         int y = 0;
  60.         for(int i = 0; i < 8; ++i){
  61.             if(m[{a + move[i].first, b + move[i].second}] > 0 && m[{a + move[i].first, b + move[i].second}] < c){
  62.                 x = a + move[i].first;
  63.                 y = b + move[i].second;
  64.                 c = m[{a + move[i].first, b + move[i].second}];
  65.             }
  66.         }
  67.         a = x;
  68.         b = y;
  69.         ans.push_back({a, b});
  70.     }
  71.     for(int i = 1; i < ans.size(); ++i){
  72.         cout << ans[ans.size() - i - 1].first << " " << ans[ans.size() - i - 1].second << "\n";
  73.     }
  74.     cout << rx << " " << ry << "\n";
  75. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement