Advertisement
Guest User

Untitled

a guest
Dec 15th, 2019
100
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.86 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <map>
  5. #include <cmath>
  6. #include <queue>
  7.  
  8. using namespace std;
  9.  
  10. struct Point {
  11. int x, y;
  12. friend bool operator <(const Point &p1, const Point &p2) {
  13. return tie(p1.x, p1.y) < tie(p2.x, p2.y);
  14. }
  15. bool operator !=(const Point &p) {
  16. return x != p.x || y != p.y;
  17. }
  18. };
  19.  
  20. int main() {
  21. int cx = 0, cy = 0, x, y, tx, ty;
  22. cin >> x >> y;
  23. while (abs(x-cx) > 2 || abs(y-cy) > 2) {
  24. if (y < cy) {
  25. if (x >= cx) {
  26. if (cy - y >= x - cx) {
  27. cx++;
  28. cy -= 2;
  29. }
  30. else {
  31. cx += 2;
  32. cy--;
  33. }
  34. }
  35. else {
  36. if (cy - y >= cx - x) {
  37. cx--;
  38. cy -= 2;
  39. }
  40. else {
  41. cx -= 2;
  42. cy--;
  43. }
  44. }
  45. }
  46. else {
  47. if (x >= cx) {
  48. if (y - cy >= x - cx) {
  49. cx++;
  50. cy += 2;
  51. }
  52. else {
  53. cx += 2;
  54. cy++;
  55. }
  56. }
  57. else {
  58. if (y - cy >= cx - x) {
  59. cx--;
  60. cy += 2;
  61. }
  62. else {
  63. cx -= 2;
  64. cy++;
  65. }
  66. }
  67. }
  68. cout << cx << " " << cy;
  69. cout << "\n";
  70. }
  71. map<Point, bool>used;
  72. map<Point, Point>pred;
  73. queue<Point>q;
  74. q.push({ cx, cy });
  75. used[{cx, cy}] = true;
  76. vector<Point>wasd = { {-1, 2}, {-1, -2}, {1, 2}, {1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1} }, path;
  77. while (!q.empty()) {
  78. if (q.front().x == x && q.front().y == y) {
  79. path.push_back({ x, y });
  80. while (pred[{x, y}] != Point{cx, cy}) {
  81. path.push_back(pred[{x, y}]);
  82. tx = pred[{x, y}].x;
  83. y = pred[{tx, y}].y;
  84. x = tx;
  85. }
  86. break;
  87. }
  88. for (auto p : wasd) {
  89. tx = q.front().x + p.x;
  90. ty = q.front().y + p.y;
  91. if (!used[{tx, ty}]) {
  92. used[{tx, ty}] = true;
  93. q.push({ tx, ty });
  94. pred[{tx, ty}] = q.front();
  95. }
  96. }
  97. q.pop();
  98. }
  99. reverse(path.begin(), path.end());
  100. for (auto v : path) {
  101. cout << v.x << " " << v.y;
  102. cout << "\n";
  103. }
  104. return 0;
  105. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement