Guest User

Untitled

a guest
Jan 18th, 2019
101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.36 KB | None | 0 0
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <ctime>
  6. #include <algorithm>
  7. #include <cstring>
  8. #include <vector>
  9. #include <set>
  10. #include <map>
  11. #include <bitset>
  12. #include <queue>
  13. #include <complex>
  14. #include <cassert>
  15.  
  16. using namespace std;
  17.  
  18. #define pb push_back
  19. #define mp make_pair
  20. #define fs first
  21. #define sc second
  22. #define sz(s) int((s).size())
  23. #define eprintf(...) fprintf(stderr, __VA_ARGS__)
  24. #define next _next
  25. #define prev _prev
  26. #define rank _rank
  27. #define y0 _fjldkl
  28.  
  29. typedef long long ll;
  30. typedef long long llong;
  31. typedef unsigned int uint;
  32. typedef unsigned long long ull;
  33. typedef vector <int> vi;
  34. typedef pair <int, int> pii;
  35. typedef complex <double> tc;
  36.  
  37. const int inf = int(1e9);
  38. const double eps = 1e-9;
  39. const double pi = 4 * atan(double(1));
  40. const int diff = 3;
  41. const int max_deep = 15;
  42. const int dx[8] = {-1, -1, -1, 0, 1, 1, 1, 0};
  43. const int dy[8] = {-1, 0, 1, 1, 1, 0, -1, -1};
  44.  
  45. struct state{
  46.     int x[4], y[4];
  47. };
  48.  
  49. int ans, x0, y0;
  50.  
  51. inline bool bad(state &cur, int x, int y){
  52.     pii p = mp(x, y);
  53.     for(int i = 1; i < 4; i++){
  54.         if(mp(cur.x[i], cur.y[i]) == p){
  55.             return true;
  56.         }
  57.     }
  58.     return false;
  59. }
  60.  
  61. inline bool fight(state &cur, int x, int y){
  62.     for(int i = 1; i < 4; i++){
  63.         if(cur.x[i] == x || cur.y[i] == y){
  64.             return true;
  65.         }
  66.     }
  67.     return false;
  68. }
  69.  
  70. inline bool can(state &cur){
  71.     vector <pii> lst;
  72.     for(int i = 0; i < 4; i++){
  73.         lst.pb(mp(cur.x[i], cur.y[i]));
  74.     }
  75.     sort(lst.begin(), lst.end());
  76.     if(unique(lst.begin(), lst.end()) != lst.end()){
  77.         return false;
  78.     }
  79.     bool fl = false;
  80.     for(int i = 0; i < 8; i++){
  81.         int x = cur.x[0] + dx[i], y = cur.y[0] + dy[i];
  82.         if(bad(cur, x, y)){
  83.             return false;
  84.         }
  85.         if(!fight(cur, x, y)){
  86.             fl = true;
  87.         }
  88.     }
  89.     if(!fl){
  90.         return false;
  91.     }
  92.     return true;
  93. }
  94.  
  95. inline bool over(state &cur){
  96.     for(int i = 0; i < 8; i++){
  97.         if(bad(cur, cur.x[0] + dx[i], cur.y[0] + dy[i])){
  98.             return false;
  99.         }
  100.     }
  101.     if(!fight(cur, cur.x[0], cur.y[0])){
  102.         return false;
  103.     }
  104.     bool fl = false;
  105.     for(int i = 0; i < 8; i++){
  106.         if(!fight(cur, cur.x[0] + dx[i], cur.y[0] + dy[i])){
  107.             return false;
  108.         }
  109.     }
  110.     return true;
  111. }
  112.  
  113. void gen(state &cur, int step, int deep){
  114.     if(deep >= ans){
  115.         return;
  116.     }
  117.     if(step == 0){
  118.         for(int i = 1; i < 4; i++){
  119.             for(int j = -diff; j <= diff; j++){
  120.                 int oy = cur.y[i];
  121.                 cur.y[i] = y0 + j;
  122.                 if(over(cur)){
  123.                     ans = deep + 1;
  124.                     cur.y[i] = oy;
  125.                     return;
  126.                 }
  127.                 if(y0 + j != oy && can(cur)){
  128.                     gen(cur, 1 - step, deep + 1);
  129.                 }
  130.                 cur.y[i] = oy;
  131.                 int ox = cur.x[i];
  132.                 cur.x[i] = x0 + j;
  133.                 if(over(cur)){
  134.                     ans = deep + 1;
  135.                     cur.x[i] = ox;
  136.                     return;
  137.                 }
  138.                 if(x0 + j != ox && can(cur)){
  139.                     gen(cur, 1 - step, deep + 1);
  140.                 }
  141.                 cur.x[i] = ox;
  142.             }
  143.         }
  144.     }
  145.     else{
  146.         for(int i = 0; i < 8; i++){
  147.             cur.x[0] += dx[i];
  148.             cur.y[0] += dy[i];
  149.             if(!fight(cur, cur.x[0], cur.y[0])){
  150.                 gen(cur, 1 - step, deep + 1);
  151.             }
  152.             cur.x[0] -= dx[i];
  153.             cur.y[0] -= dy[i];
  154.         }
  155.     }
  156. }
  157.  
  158. void go(state &cur){
  159.     x0 = cur.x[0];
  160.     y0 = cur.y[0];
  161.     int best_ans = inf, a = -1, b = -1, c = -1;
  162.     for(int i = 1; i < 4; i++){
  163.         for(int j = -diff; j <= diff; j++){
  164.             int oy = cur.y[i];
  165.             cur.y[i] = y0 + j;
  166.             if(over(cur)){
  167.                 cout << i << " " << 0 << " " << y0 + j - oy << endl;
  168.                 return;
  169.             }
  170.             if(y0 + j != oy && can(cur)){
  171.                 ans = max_deep;
  172.                 gen(cur, 1, 0);
  173.                 if(ans < best_ans){
  174.                     ans = best_ans;
  175.                     a = i;
  176.                     b = j;
  177.                     c = 0;
  178.                 }
  179.             }
  180.             cur.y[i] = oy;
  181.             int ox = cur.x[i];
  182.             cur.x[i] = x0 + j;
  183.             if(over(cur)){
  184.                 cout << i << " " << x0 + j - ox << " " << 0 << endl;
  185.                 return;
  186.             }
  187.             if(x0 + j != ox && can(cur)){
  188.                 ans = max_deep;
  189.                 gen(cur, 1, 0);
  190.                 if(ans < best_ans){
  191.                     ans = best_ans;
  192.                     a = i;
  193.                     b = j;
  194.                     c = 1;
  195.                 }
  196.             }
  197.             cur.x[i] = ox;
  198.         }
  199.     }
  200.     if(c == 0){
  201.         cout << a << " " << 0 << " " << y0 + b - cur.y[0] << endl;
  202.         cur.y[a] = y0 + b;
  203.     }
  204.     else{
  205.         cout << a << " " << x0 + b - cur.x[0] << " " << 0 << endl;
  206.         cur.x[a] = x0 + b;
  207.     }
  208.     int vx, vy;
  209.     cin >> vx >> vy;
  210.     cur.x[0] += vx;
  211.     cur.y[0] += vy;
  212.     go(cur);
  213. }
  214.  
  215. int main(){
  216.     //freopen("input.txt", "r", stdin);
  217.     //freopen("output.txt", "w", stdout);
  218.     //freopen("sum.in", "r", stdin);
  219.     //freopen("sum.out", "w", stdout);
  220.     state cur;
  221.     for(int i = 0; i < 4; i++){
  222.         cin >> cur.x[i] >> cur.y[i];
  223.     }
  224.     go(cur);
  225.     return 0;
  226. }
Add Comment
Please, Sign In to add comment