Advertisement
Guest User

Untitled

a guest
Feb 23rd, 2018
64
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 7.50 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. #define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  4. #define ll long long
  5. #define ld long double
  6. #define EPS (1e-6)
  7. #define mod 1000000007
  8. #define pii pair<ll, ll>
  9. #define piii pair<pii, ll>
  10. #define SIZE(x) (int) x.size()
  11. #define to_string(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
  12. #define lp(i, a, n) for (int(i) = (a); (i) <= (int)(n); ++(i))
  13. #define lpd(i, n, a) for (int(i) = (n); (i) >= (a); --(i))
  14. #define bitcount(n) __builtin_popcountll(n)
  15. #define readi(x) scanf("%d", &x);
  16. #define readl(x) scanf("%lld", &x);
  17. #define reads(x) scanf("%s", &x);
  18. #define readc(x) scanf("%c", &x);
  19. #define readd(x) scanf("%lf", &x);
  20.  
  21. using namespace std;
  22. const int N = 300005;
  23. const ll OO = (1ll << 60);
  24. int t, x, y, xx, yy;
  25. vector<pii> cur, toTry;
  26. set<pii> vv;
  27.  
  28. bool isin(int x, int y) {
  29. return x >= 0 && x <= 7 && y >= 0 && y <= 7;
  30. }
  31.  
  32. bool danger(int x, int y) {
  33. for (auto tmp : cur) {
  34. if (tmp.first == x || tmp.second == y)
  35. return true;
  36. if (abs(tmp.first - x) == abs(tmp.second - y))
  37. return true;
  38. }
  39. return false;
  40. }
  41.  
  42. bool isprotected(int idx) {
  43. bool danger = false;
  44. lp (i, cur[idx].first - 1, cur[idx].first + 1) {
  45. lp (j, cur[idx].second - 1, cur[idx].second + 1) {
  46. if (cur[idx].first == i && cur[idx].second)
  47. continue;
  48. if (!isin(i, j))
  49. continue;
  50. if ((i == x && j == y) || (i == xx && j == y))
  51. danger = true;
  52. if (danger)
  53. break;
  54. }
  55. if (danger)
  56. break;
  57. }
  58. if (danger) {
  59. lp (i, 0, SIZE(cur) - 1) {
  60. if (i == idx)
  61. continue;
  62. if (cur[idx].first == cur[i].first || cur[idx].second == cur[i].second)
  63. return true;
  64. if (abs(cur[idx].first - cur[i].first) == abs(cur[idx].second - cur[i].second))
  65. return true;
  66. }
  67. }
  68. else
  69. return true;
  70. return false;
  71. }
  72.  
  73. bool check() {
  74. lp (i, x - 1, x + 1) {
  75. lp (j, y - 1, y + 1) {
  76. if(isin(i, j) && !danger(i, j))
  77. return false;
  78. }
  79. }
  80. lp (i, xx - 1, xx + 1) {
  81. lp (j, yy - 1, yy + 1) {
  82. if(isin(i, j) && !danger(i, j))
  83. return false;
  84. }
  85. }
  86. lp (i, 0, SIZE(cur) - 1)
  87. if (!isprotected(i))
  88. return false;
  89. return true;
  90. }
  91.  
  92. bool setQ(int idx, int can) {
  93. if (idx == SIZE(toTry) || !can)
  94. return check();
  95. if (setQ(idx + 1, can))
  96. return true;
  97. cur.push_back(toTry[idx]);
  98. if (setQ(idx + 1, can - 1))
  99. return true;
  100. cur.pop_back();
  101. return false;
  102. }
  103.  
  104. int main() {
  105. // freopen("input.txt", "r", stdin);
  106. // freopen("output.txt", "w", stdout);
  107. cin >> t;
  108. while (t--) {
  109. cin >> x >> y >> xx >> yy;
  110. toTry.clear(), vv.clear();
  111. lp (i, x - 2, x + 2) {
  112. lp (j, y - 2, y + 2) {
  113. if ((i == x && j == y) || (i == xx && j == yy) || !isin(i, j))
  114. continue;
  115. vv.insert({i, j});
  116. }
  117. }
  118. lp (i, xx - 2, xx + 2) {
  119. lp (j, yy - 2, yy + 2) {
  120. if ((i == x && j == y) || (i == xx && j == yy) || !isin(i, j))
  121. continue;
  122. vv.insert({i, j});
  123. }
  124. }
  125. for (auto tmp : vv)
  126. toTry.push_back(tmp);
  127. bool ans = false;
  128. lp (i, 2, 3) {
  129. if (setQ(0, i)) {
  130. cout << i << endl;
  131. for (auto d : cur)
  132. cout << "Q " << d.first << " " << d.second << endl;
  133. ans = true;
  134. cur.clear();
  135. }
  136. if (ans)
  137. break;
  138. }
  139. if (!ans) {
  140. cout << 4 << endl;
  141. if (isin(x + 1, y) && isin(x + 1, y + 1) && !((x + 1 == xx && y == yy) || (x + 1 == xx && y + 1 == yy)))
  142. cout << "Q " << x + 1 << " " << y << endl << "Q " << x + 1 << " " << y + 1 << endl;
  143. else if (isin(x + 1, y) && isin(x + 1, y - 1) && !((x + 1 == xx && y == yy) || (x + 1 == xx && y - 1 == yy)))
  144. cout << "Q " << x + 1 << " " << y << endl << "Q " << x + 1 << " " << y - 1 << endl;
  145.  
  146. else if (isin(x - 1, y) && isin(x - 1, y + 1) && !((x - 1 == xx && y == yy) || (x - 1 == xx && y + 1 == yy)))
  147. cout << "Q " << x - 1 << " " << y << endl << "Q " << x - 1 << " " << y + 1 << endl;
  148. else if (isin(x - 1, y) && isin(x - 1, y - 1) && !((x - 1 == xx && y == yy) || (x - 1 == xx && y - 1 == yy)))
  149. cout << "Q " << x - 1 << " " << y << endl << "Q " << x - 1 << " " << y - 1 << endl;
  150.  
  151. else if (isin(x, y + 1) && isin(x + 1, y + 1) && !((x == xx && y + 1 == yy) || (x + 1 == xx && y + 1 == yy)))
  152. cout << "Q " << x << " " << y + 1 << endl << "Q " << x + 1 << " " << y + 1 << endl;
  153. else if (isin(x, y + 1) && isin(x - 1, y + 1) && !((x == xx && y + 1 == yy) || (x - 1 == xx && y + 1 == yy)))
  154. cout << "Q " << x << " " << y + 1 << endl << "Q " << x - 1 << " " << y + 1 << endl;
  155.  
  156. else if (isin(x, y - 1) && isin(x + 1, y - 1) && !((x == xx && y - 1 == yy) || (x + 1 == xx && y - 1 == yy)))
  157. cout << "Q " << x << " " << y - 1 << endl << "Q " << x + 1 << " " << y - 1 << endl;
  158. else if (isin(x, y - 1) && isin(x - 1, y - 1) && !((x == xx && y - 1 == yy) || (x - 1 == xx && y - 1 == yy)))
  159. cout << "Q " << x << " " << y - 1 << endl << "Q " << x - 1 << " " << y - 1 << endl;
  160.  
  161. if (isin(xx + 1, yy) && isin(xx + 1, yy + 1) && !((xx + 1 == x && yy == y) || (xx + 1 == x && yy + 1 == y)))
  162. cout << "Q " << xx + 1 << " " << yy << endl << "Q " << xx + 1 << " " << yy + 1 << endl;
  163. else if (isin(xx + 1, yy) && isin(xx + 1, yy - 1) && !((xx + 1 == x && yy == y) || (xx + 1 == x && yy - 1 == y)))
  164. cout << "Q " << xx + 1 << " " << yy << endl << "Q " << xx + 1 << " " << yy - 1 << endl;
  165.  
  166. else if (isin(xx - 1, yy) && isin(xx - 1, yy + 1) && !((xx - 1 == x && yy == y) || (xx - 1 == x && yy + 1 == y)))
  167. cout << "Q " << xx - 1 << " " << yy << endl << "Q " << xx - 1 << " " << yy + 1 << endl;
  168. else if (isin(xx - 1, yy) && isin(xx - 1, yy - 1) && !((xx - 1 == x && yy == y) || (xx - 1 == x && yy - 1 == y)))
  169. cout << "Q " << xx - 1 << " " << yy << endl << "Q " << xx - 1 << " " << yy - 1 << endl;
  170.  
  171. else if (isin(xx, yy + 1) && isin(xx + 1, yy + 1) && !((xx == x && yy + 1 == y) || (xx + 1 == x && yy + 1 == y)))
  172. cout << "Q " << xx << " " << yy + 1 << endl << "Q " << xx + 1 << " " << yy + 1 << endl;
  173. else if (isin(xx, yy + 1) && isin(xx - 1, yy + 1) && !((xx == x && yy + 1 == y) || (xx - 1 == x && yy + 1 == y)))
  174. cout << "Q " << xx << " " << yy + 1 << endl << "Q " << xx - 1 << " " << yy + 1 << endl;
  175.  
  176. else if (isin(xx, yy - 1) && isin(xx + 1, yy - 1) && !((xx == x && yy - 1 == y) || (xx + 1 == x && yy - 1 == y)))
  177. cout << "Q " << xx << " " << yy - 1 << endl << "Q " << xx + 1 << " " << yy - 1 << endl;
  178. else if (isin(xx, yy - 1) && isin(xx - 1, yy - 1) && !((xx == x && yy - 1 == y) || (xx - 1 == x && yy - 1 == y)))
  179. cout << "Q " << xx << " " << yy - 1 << endl << "Q " << xx - 1 << " " << yy - 1 << endl;
  180. }
  181. }
  182. return 0;
  183. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement