Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define io ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- #define ll long long
- #define ld long double
- #define EPS (1e-6)
- #define mod 1000000007
- #define pii pair<ll, ll>
- #define piii pair<pii, ll>
- #define SIZE(x) (int) x.size()
- #define to_string(x) static_cast<std::ostringstream&>((std::ostringstream() << std::dec << x)).str()
- #define lp(i, a, n) for (int(i) = (a); (i) <= (int)(n); ++(i))
- #define lpd(i, n, a) for (int(i) = (n); (i) >= (a); --(i))
- #define bitcount(n) __builtin_popcountll(n)
- #define readi(x) scanf("%d", &x);
- #define readl(x) scanf("%lld", &x);
- #define reads(x) scanf("%s", &x);
- #define readc(x) scanf("%c", &x);
- #define readd(x) scanf("%lf", &x);
- using namespace std;
- const int N = 300005;
- const ll OO = (1ll << 60);
- int t, x, y, xx, yy;
- vector<pii> cur, toTry;
- set<pii> vv;
- bool isin(int x, int y) {
- return x >= 0 && x <= 7 && y >= 0 && y <= 7;
- }
- bool danger(int x, int y) {
- for (auto tmp : cur) {
- if (tmp.first == x || tmp.second == y)
- return true;
- if (abs(tmp.first - x) == abs(tmp.second - y))
- return true;
- }
- return false;
- }
- bool isprotected(int idx) {
- bool danger = false;
- lp (i, cur[idx].first - 1, cur[idx].first + 1) {
- lp (j, cur[idx].second - 1, cur[idx].second + 1) {
- if (cur[idx].first == i && cur[idx].second)
- continue;
- if (!isin(i, j))
- continue;
- if ((i == x && j == y) || (i == xx && j == y))
- danger = true;
- if (danger)
- break;
- }
- if (danger)
- break;
- }
- if (danger) {
- lp (i, 0, SIZE(cur) - 1) {
- if (i == idx)
- continue;
- if (cur[idx].first == cur[i].first || cur[idx].second == cur[i].second)
- return true;
- if (abs(cur[idx].first - cur[i].first) == abs(cur[idx].second - cur[i].second))
- return true;
- }
- }
- else
- return true;
- return false;
- }
- bool check() {
- lp (i, x - 1, x + 1) {
- lp (j, y - 1, y + 1) {
- if(isin(i, j) && !danger(i, j))
- return false;
- }
- }
- lp (i, xx - 1, xx + 1) {
- lp (j, yy - 1, yy + 1) {
- if(isin(i, j) && !danger(i, j))
- return false;
- }
- }
- lp (i, 0, SIZE(cur) - 1)
- if (!isprotected(i))
- return false;
- return true;
- }
- bool setQ(int idx, int can) {
- if (idx == SIZE(toTry) || !can)
- return check();
- if (setQ(idx + 1, can))
- return true;
- cur.push_back(toTry[idx]);
- if (setQ(idx + 1, can - 1))
- return true;
- cur.pop_back();
- return false;
- }
- int main() {
- // freopen("input.txt", "r", stdin);
- // freopen("output.txt", "w", stdout);
- cin >> t;
- while (t--) {
- cin >> x >> y >> xx >> yy;
- toTry.clear(), vv.clear();
- lp (i, x - 2, x + 2) {
- lp (j, y - 2, y + 2) {
- if ((i == x && j == y) || (i == xx && j == yy) || !isin(i, j))
- continue;
- vv.insert({i, j});
- }
- }
- lp (i, xx - 2, xx + 2) {
- lp (j, yy - 2, yy + 2) {
- if ((i == x && j == y) || (i == xx && j == yy) || !isin(i, j))
- continue;
- vv.insert({i, j});
- }
- }
- for (auto tmp : vv)
- toTry.push_back(tmp);
- bool ans = false;
- lp (i, 2, 3) {
- if (setQ(0, i)) {
- cout << i << endl;
- for (auto d : cur)
- cout << "Q " << d.first << " " << d.second << endl;
- ans = true;
- cur.clear();
- }
- if (ans)
- break;
- }
- if (!ans) {
- cout << 4 << endl;
- if (isin(x + 1, y) && isin(x + 1, y + 1) && !((x + 1 == xx && y == yy) || (x + 1 == xx && y + 1 == yy)))
- cout << "Q " << x + 1 << " " << y << endl << "Q " << x + 1 << " " << y + 1 << endl;
- else if (isin(x + 1, y) && isin(x + 1, y - 1) && !((x + 1 == xx && y == yy) || (x + 1 == xx && y - 1 == yy)))
- cout << "Q " << x + 1 << " " << y << endl << "Q " << x + 1 << " " << y - 1 << endl;
- else if (isin(x - 1, y) && isin(x - 1, y + 1) && !((x - 1 == xx && y == yy) || (x - 1 == xx && y + 1 == yy)))
- cout << "Q " << x - 1 << " " << y << endl << "Q " << x - 1 << " " << y + 1 << endl;
- else if (isin(x - 1, y) && isin(x - 1, y - 1) && !((x - 1 == xx && y == yy) || (x - 1 == xx && y - 1 == yy)))
- cout << "Q " << x - 1 << " " << y << endl << "Q " << x - 1 << " " << y - 1 << endl;
- else if (isin(x, y + 1) && isin(x + 1, y + 1) && !((x == xx && y + 1 == yy) || (x + 1 == xx && y + 1 == yy)))
- cout << "Q " << x << " " << y + 1 << endl << "Q " << x + 1 << " " << y + 1 << endl;
- else if (isin(x, y + 1) && isin(x - 1, y + 1) && !((x == xx && y + 1 == yy) || (x - 1 == xx && y + 1 == yy)))
- cout << "Q " << x << " " << y + 1 << endl << "Q " << x - 1 << " " << y + 1 << endl;
- else if (isin(x, y - 1) && isin(x + 1, y - 1) && !((x == xx && y - 1 == yy) || (x + 1 == xx && y - 1 == yy)))
- cout << "Q " << x << " " << y - 1 << endl << "Q " << x + 1 << " " << y - 1 << endl;
- else if (isin(x, y - 1) && isin(x - 1, y - 1) && !((x == xx && y - 1 == yy) || (x - 1 == xx && y - 1 == yy)))
- cout << "Q " << x << " " << y - 1 << endl << "Q " << x - 1 << " " << y - 1 << endl;
- if (isin(xx + 1, yy) && isin(xx + 1, yy + 1) && !((xx + 1 == x && yy == y) || (xx + 1 == x && yy + 1 == y)))
- cout << "Q " << xx + 1 << " " << yy << endl << "Q " << xx + 1 << " " << yy + 1 << endl;
- else if (isin(xx + 1, yy) && isin(xx + 1, yy - 1) && !((xx + 1 == x && yy == y) || (xx + 1 == x && yy - 1 == y)))
- cout << "Q " << xx + 1 << " " << yy << endl << "Q " << xx + 1 << " " << yy - 1 << endl;
- else if (isin(xx - 1, yy) && isin(xx - 1, yy + 1) && !((xx - 1 == x && yy == y) || (xx - 1 == x && yy + 1 == y)))
- cout << "Q " << xx - 1 << " " << yy << endl << "Q " << xx - 1 << " " << yy + 1 << endl;
- else if (isin(xx - 1, yy) && isin(xx - 1, yy - 1) && !((xx - 1 == x && yy == y) || (xx - 1 == x && yy - 1 == y)))
- cout << "Q " << xx - 1 << " " << yy << endl << "Q " << xx - 1 << " " << yy - 1 << endl;
- else if (isin(xx, yy + 1) && isin(xx + 1, yy + 1) && !((xx == x && yy + 1 == y) || (xx + 1 == x && yy + 1 == y)))
- cout << "Q " << xx << " " << yy + 1 << endl << "Q " << xx + 1 << " " << yy + 1 << endl;
- else if (isin(xx, yy + 1) && isin(xx - 1, yy + 1) && !((xx == x && yy + 1 == y) || (xx - 1 == x && yy + 1 == y)))
- cout << "Q " << xx << " " << yy + 1 << endl << "Q " << xx - 1 << " " << yy + 1 << endl;
- else if (isin(xx, yy - 1) && isin(xx + 1, yy - 1) && !((xx == x && yy - 1 == y) || (xx + 1 == x && yy - 1 == y)))
- cout << "Q " << xx << " " << yy - 1 << endl << "Q " << xx + 1 << " " << yy - 1 << endl;
- else if (isin(xx, yy - 1) && isin(xx - 1, yy - 1) && !((xx == x && yy - 1 == y) || (xx - 1 == x && yy - 1 == y)))
- cout << "Q " << xx << " " << yy - 1 << endl << "Q " << xx - 1 << " " << yy - 1 << endl;
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement