結果
| 問題 | No.3336 Coincidence |
| コンテスト | |
| ユーザー |
 ecottea
|
| 提出日時 | 2025-11-14 15:41:40 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
RE
|
| 実行時間 | - |
| コード長 | 23,783 bytes |
| コンパイル時間 | 6,979 ms |
| コンパイル使用メモリ | 346,036 KB |
| 実行使用メモリ | 7,716 KB |
| 最終ジャッジ日時 | 2025-11-14 15:42:04 |
| 合計ジャッジ時間 | 22,598 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 31 RE * 2 |
ソースコード
// QCFium 法
//#pragma GCC target("avx2") // yukicoder では消す
#pragma GCC optimize("O3") // たまにバグる
#pragma GCC optimize("unroll-loops")
#ifndef HIDDEN_IN_VS // 折りたたみ用
// 警告の抑制
#define _CRT_SECURE_NO_WARNINGS
// ライブラリの読み込み
#include <bits/stdc++.h>
using namespace std;
// 型名の短縮
using ll = long long; using ull = unsigned long long; // -2^63 ～ 2^63 = 9e18（int は -2^31 ～ 2^31 = 2e9）
using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>;
using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vvvvi = vector<vvvi>;
using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vvvvl = vector<vvvl>;
using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>;
using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>;
using Graph = vvi;
// 定数の定義
const double PI = acos(-1);
int DX[4] = { 1, 0, -1, 0 }; // 4 近傍（下，右，上，左）
int DY[4] = { 0, 1, 0, -1 };
int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;
// 入出力高速化
struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp;
// 汎用マクロの定義
#define all(a) (a).begin(), (a).end()
#define sz(x) ((int)(x).size())
#define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), (x)))
#define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), (x)))
#define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");}
#define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順
#define repe(v, a) for(const auto& v : (a)) // a の全要素（変更不可能）
#define repea(v, a) for(auto& v : (a)) // a の全要素（変更可能）
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define repis(i, set) for(int i = lsb(set), bset##i = set; i < 32; bset##i -= 1 << i, i = lsb(bset##i)) // set の全要素（昇順）
#define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て（昇順）
#define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去
#define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了
#define inQ(x, y, u, l, d, r) ((u) <= (x) && (l) <= (y) && (x) < (d) && (y) < (r)) // 半開矩形内判定
// 汎用関数の定義
template <class T> inline ll powi(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; }
template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline T smod(T n, T m) { n %= m; if (n < 0) n += m; return n; } // 非負mod
// 演算子オーバーロード
template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; }
template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; }
template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; }
template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; }
#endif // 折りたたみ用
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#ifdef _MSC_VER
#include "localACL.hpp"
#endif
using mint = modint998244353;
//using mint = static_modint<(int)1e9+7>;
//using mint = modint; // mint::set_mod(m);
using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; using vvvvm = vector<vvvm>; using pim = pair<int, mint>;
#endif
#ifdef _MSC_VER // 手元環境（Visual Studio）
#include "local.hpp"
#else // 提出用（gcc）
int mute_dump = 0;
int frac_print = 0;
#if __has_include(<atcoder/all>)
namespace atcoder {
inline istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; }
inline ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; }
}
#endif
inline int popcount(int n) { return __builtin_popcount(n); }
inline int popcount(ll n) { return __builtin_popcountll(n); }
inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : 32; }
inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : 64; }
inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; }
inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; }
#define dump(...)
#define dumpel(v)
#define dump_math(v)
#define input_from_file(f)
#define output_to_file(f)
#define Assert(b) { if (!(b)) { vc MLE(1<<30); EXIT(MLE.back()); } } // RE の代わりに MLE を出す
#endif
//【平面上の点，二次元ベクトル】
/*
* 平面における点／二次元ベクトルを表す構造体
*
* Point<T>() : O(1)
* (0, 0) で初期化する．
*
* Point<T>(T x, T y) : O(1)
* (x, y) で初期化する．
*
* p1 == p2, p1 != p2, p1 < p2, p1 > p2, p1 <= p2, p1 >= p2 : O(1)
* x 座標優先，次いで y 座標の大小比較を行う．
*
* p1 + p2, p1 - p2, c * p, p * c, p / c : O(1)
* ベクトルとみなした加算，減算，スカラー倍，スカラー除算を行う．複合代入演算子も使用可．
*
* T sqnorm() : O(1)
* 自身の 2 乗ノルムを返す．
*
* double norm() : O(1)
* 自身のノルムを返す．
*
* Point<double> normalize() : O(1)
* 自身を正規化したベクトルを返す．
*
* T dot(Point<T> p) : O(1)
* 自身と p との内積を返す．
*
* T cross(Point<T> p) : O(1)
* 自身と p との外積を返す．
*
* double angle(Point<T> p) : O(1)
* 自身から p までの成す角度を返す．
*/
template <class T>
struct Point {
// 点の x 座標，y 座標
T x, y;
// コンストラクタ
Point() : x(0), y(0) {}
Point(T x_, T y_) : x(x_), y(y_) {}
// 代入
Point(const Point& old) = default;
Point& operator=(const Point& other) = default;
// キャスト
operator Point<ll>() const { return Point<ll>((ll)x, (ll)y); }
operator Point<double>() const { return Point<double>((double)x, (double)y); }
// 入出力
friend istream& operator>>(istream& is, Point& p) { is >> p.x >> p.y; return is; }
friend ostream& operator<<(ostream& os, const Point& p) { os << '(' << p.x << ',' << p.y << ')'; return os; }
// 比較（x 座標優先）
bool operator==(const Point& p) const { return x == p.x && y == p.y; }
bool operator!=(const Point& p) const { return !(*this == p); }
bool operator<(const Point& p) const { return x == p.x ? y < p.y : x < p.x; }
bool operator>=(const Point& p) const { return !(*this < p); }
bool operator>(const Point& p) const { return x == p.x ? y > p.y : x > p.x; }
bool operator<=(const Point& p) const { return !(*this > p); }
// 加算，減算，スカラー倍，スカラー除算
Point& operator+=(const Point& p) { x += p.x; y += p.y; return *this; }
Point operator+(const Point& p) const { Point q(*this); return q += p; }
Point& operator-=(const Point& p) { x -= p.x; y -= p.y; return *this; }
Point operator-(const Point& p) const { Point q(*this); return q -= p; }
Point& operator*=(const T& c) { x *= c; y *= c; return *this; }
Point operator*(const T& c) const { Point q(*this); return q *= c; }
Point& operator/=(const T& c) { x /= c; y /= c; return *this; }
Point operator/(const T& c) const { Point q(*this); return q /= c; }
friend Point operator*(const T& sc, const Point& p) { return p * sc; }
Point operator-() const { Point a = *this; return a *= -1; }
// 二乗ノルム，ノルム，正規化
T sqnorm() const { return x * x + y * y; }
double norm() const { return sqrt((double)x * x + (double)y * y); }
Point<double> normalize() const { return Point<double>(*this) / norm(); }
// 内積，外積，成す角度
T dot(const Point& other) const { return x * other.x + y * other.y; }
T cross(const Point& other) const { return x * other.y - y * other.x; }
double angle(const Point& other) const {
return atan2(this->cross(other), this->dot(other));
}
};
//【平面内の直線，線分】
/*
* {a, b} : 2 点 a, b を通る a → b 方向の有向直線を表す．
*
* その他，無向直線，有向線分，無向線分などを表すのにも用いる．
*/
template <class T>
using Line = pair<Point<T>, Point<T>>;
//【点と有向線分の位置関係】O(1)
/*
* 点 p と有向線分 s = a → b の位置関係を返す．
*
* 戻り値：
* 1 : p が s の左側にある場合（a → b → p が反時計回り）
* -1 : p が s の右側にある場合（a → b → p が時計回り）
* 2 : p が s の b より先にある場合（a < b < p 順）
* -2 : p が s の a より後ろにある場合（p < a < b 順）
* 0 : p が s 上にある場合（a ≦ p ≦ b 順）
*/
template <typename T>
inline int ccw(const Point<T>& p, const Line<T>& s) {
// verify : https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_1_C
auto op = (s.second - s.first).cross(p - s.first);
if (op > T(0)) {
// p が s の左側にある
return 1;
}
else if (op < T(0)) {
// p が s の右側にある
return -1;
}
else {
if ((s.first - s.second).dot(p - s.second) < T(0)) {
// p が s の前にある
return 2;
}
else if ((s.second - s.first).dot(p - s.first) < T(0)) {
// p が s の後ろにある
return -2;
}
else {
// p が s 上にある
return 0;
}
}
}
//【共有判定（閉線分と閉線分）】O(1)
/*
* 閉線分 s1 と閉線分 s2 が共有点をもつなら true，さもなくば false を返す．
*
* 利用：【点と有向線分の位置関係】
*/
template <typename T>
inline bool intersectQ_CS_CS(const Line<T>& s1, const Line<T>& s2) {
// verify : https://onlinejudge.u-aizu.ac.jp/courses/library/4/CGL/all/CGL_2_B
// 共有点をもつ
// ⇔ (s1 の両端が s2 について逆側，かつ，s2 の両端が s1 について逆側)
// または (s1 の端点が s2 上) または (s2 の端点が s1 上)
//
// 端点が線分の逆側のとき ccw() の符号が異なり，
// 端点が線分上のとき ccw() = 0 となるので，綺麗にまとめられる．
return ccw(s2.first, s1) * ccw(s2.second, s1) <= 0 &&
ccw(s1.first, s2) * ccw(s1.second, s2) <= 0;
}
using P = Point<int>;
vector<pii> WA(vector<P> p) {
dump(p);
if (abs(p[0].x - p[1].x) + abs(p[0].y - p[1].y) <= 1) return vector<pii>();
if (abs(p[2].x - p[3].x) + abs(p[2].y - p[3].y) <= 1) return vector<pii>();
if (abs(p[0].x + p[0].y + p[2].x + p[2].y) & 1) return vector<pii>();
int L = 185;
vector<P> e(4);
e[0] = { 1, 0 };
e[1] = { 0, 1 };
e[2] = { -1, 0 };
e[3] = { 0, -1 };
{
vvi dirss{
{3, 1, 2, 0},
{3, 1, 0, 2},
{1, 3, 2, 0},
{1, 3, 0, 2},
{2, 0, 3, 1},
{2, 0, 1, 3},
{0, 2, 3, 1},
{0, 2, 1, 3}
};
repe(dirs, dirss) {
bool ok = true;
rep(i, 4) repi(j, i + 1, 3) {
{
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[i] + 1, 4)];
Line<int> li = { p[i] + dd, p[i] + dd + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[i] - 1, 4)];
Line<int> li = { p[i] + dd, p[i] + dd + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[j] + 1, 4)];
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j] + dd, p[j] + dd + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[j] - 1, 4)];
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j] + dd, p[j] + dd + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
}
if (!ok) continue;
set<P> load, wall;
rep(i, 4) {
auto q = p[i];
while (max(abs(q.x), abs(q.y)) < L) {
load.insert(q);
rep(k, 4) wall.insert(q + e[k]);
q += e[dirs[i]];
}
}
repi(x, -L + 1, L - 1) {
wall.insert(P(x, -L + 1));
wall.insert(P(x, L - 1));
}
repi(y, -L + 1, L - 1) {
wall.insert(P(-L + 1, y));
wall.insert(P(L - 1, y));
}
repi(i, L, 2 * L) {
wall.insert(i * (e[dirs[0]] + e[dirs[2]]));
}
repe(q, load) {
if (wall.count(q)) {
wall.erase(q);
}
}
vector<pii> res;
repe(q, wall) {
res.push_back({ q.x, q.y });
}
return res;
}
}
{
vvi dirss{
{0, 1, 2, 3},
{1, 2, 3, 0},
{2, 3, 0, 1},
{3, 0, 1, 2},
{0, 3, 2, 1},
{3, 2, 1, 0},
{2, 1, 0, 3},
{1, 0, 3, 2}
};
repe(dirs, dirss) {
bool ok = true;
rep(i, 4) repi(j, i + 1, 3) {
{
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[i] + 1, 4)];
Line<int> li = { p[i] + dd, p[i] + dd + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[i] - 1, 4)];
Line<int> li = { p[i] + dd, p[i] + dd + 99999 * e[dirs[i]] };
Line<int> lj = { p[j], p[j] + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[j] + 1, 4)];
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j] + dd, p[j] + dd + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
{
auto dd = e[smod(dirs[j] - 1, 4)];
Line<int> li = { p[i], p[i] + 99999 * e[dirs[i]] };
Line<int> lj = { p[j] + dd, p[j] + dd + 99999 * e[dirs[j]] };
if (intersectQ_CS_CS(li, lj)) ok = false;
}
}
if (!ok) continue;
set<P> load, wall;
rep(i, 4) {
auto q = p[i];
while (max(abs(q.x), abs(q.y)) < L) {
load.insert(q);
rep(k, 4) wall.insert(q + e[k]);
q += e[dirs[i]];
}
}
repi(x, -L + 1, L - 1) {
wall.insert(P(x, -L + 1));
wall.insert(P(x, L - 1));
}
repi(y, -L + 1, L - 1) {
wall.insert(P(-L + 1, y));
wall.insert(P(L - 1, y));
}
repi(i, L, 2 * L) {
wall.insert(i * (e[dirs[2]] + e[dirs[3]]));
}
repe(q, load) {
if (wall.count(q)) {
wall.erase(q);
}
}
vector<pii> res;
repe(q, wall) {
res.push_back({ q.x, q.y });
}
return res;
}
}
return vector<pii>();
}
//【迷路】O(h w)
/*
* 壁が wall で表された h×w の迷路 c について，スタート (sx, sy) から
* 各マス c[i][j] への最短経路長（到達不能なら INF）を返す．
*
*（格子上の幅優先探索）
*/
template <class T>
vvi solve_maze(const vector<vector<T>>& c, int sx, int sy, const T wall = '#') {
// verify : https://atcoder.jp/contests/abc317/tasks/abc317_e
int h = sz(c), w = sz(c[0]);
vvi dist(h, vi(w, INF));
if (c[sx][sy] == wall) return dist;
dist[sx][sy] = 0;
// q : 未探索のマスを記録しておくキュー
queue<pii> q;
q.push({ sx, sy });
while (!q.empty()) {
auto [x, y] = q.front(); q.pop();
// マス (x, y) の 4 近傍を調べる．
rep(k, 4) {
// (nx, ny) : (x, y) の近傍の座標
int nx = x + DX[k];
int ny = y + DY[k];
// 範囲外または壁マスなら何もしない．
if (!inQ(nx, ny, 0, 0, h, w) || c[nx][ny] == wall) continue;
// 既に最短経路長が確定済みなら何もしない．
if (dist[nx][ny] != INF) continue;
// 最短経路長の確定
dist[nx][ny] = dist[x][y] + 1;
q.push({ nx, ny });
}
}
return dist;
}
vector<pii> solveAC(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy, bool rev) {
int L = 105;
//L = 5;
vvc G(2 * L + 1, vc(2 * L + 1, '.'));
rep(k, 4) {
G[bx + DX[k] + L][by + DY[k] + L] = '#';
G[dx + DX[k] + L][dy + DY[k] + L] = '#';
}
auto dist = solve_maze(G, ax + L, ay + L);
int dist_ac = dist[cx + L][cy + L];
dump("dist_ac:", dist_ac);
if (dist_ac == INF) return vector<pii>();
if (rev) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
int x = cx, y = cy; vector<pii> path_ac{ {x,y} };
while (x != ax || y != ay) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_ac.push_back({ x, y });
}
dump("path_ac:", path_ac);
if (rev) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
rep(k, 4) {
G[bx + DX[k] + L][by + DY[k] + L] = '.';
G[dx + DX[k] + L][dy + DY[k] + L] = '.';
}
auto [mx, my] = path_ac[dist_ac / 2];
for (auto [x, y] : path_ac) {
if (x == mx && y == my) continue;
rep(k, 4) {
G[x + DX[k] + L][y + DY[k] + L] = '#';
}
}
G[mx + L][my + L] = '.';
G[bx + L][by + L] = '.';
G[dx + L][dy + L] = '#';
//dumpel(G);
dist = solve_maze(G, mx + L, my + L);
if (dist[bx + L][by + L] == INF) return vector<pii>();
x = bx, y = by; vector<pii> path_mb{ {x,y} };
while (x != mx || y != my) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_mb.push_back({ x, y });
}
dump("path_mb:", path_mb);
G[bx + L][by + L] = '#';
G[dx + L][dy + L] = '.';
//dumpel(G);
dist = solve_maze(G, mx + L, my + L);
if (dist[dx + L][dy + L] == INF) return vector<pii>();
x = dx, y = dy; vector<pii> path_md{ {x,y} };
while (x != mx || y != my) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_md.push_back({ x, y });
}
dump("path_md:", path_md);
set<pii> walls;
for (auto [x, y] : path_ac) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_mb) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_md) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_ac) {
walls.erase({ x, y });
}
for (auto [x, y] : path_mb) {
walls.erase({ x, y });
}
for (auto [x, y] : path_md) {
walls.erase({ x, y });
}
return vector<pii>(all(walls));
}
/*
これでダメなケース：
...D ....C.
..C. D..oo.
.B.. ...o.B
A... .Aoo..
*/
vector<pii> solveAD(int ax, int ay, int bx, int by, int cx, int cy, int dx, int dy,
bool rev, bool rev2, bool rev3, bool rev4, int lx, int ly, int e1, int e2)
{
int L = 200;
//L = 5;
vvc G(2 * L + 1, vc(2 * L + 1, '.'));
rep(k, 4) {
G[bx + DX[k] + L][by + DY[k] + L] = '#';
G[cx + DX[k] + L][cy + DY[k] + L] = '#';
}
auto dist = solve_maze(G, ax + L, ay + L);
if (dist[dx + L][dy + L] == INF) return vector<pii>();
if (rev) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
int x = dx, y = dy; vector<pii> path_ad{ {x,y} };
while (x != ax || y != ay) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_ad.push_back({ x, y });
}
dump("path_ad:", path_ad);
if (rev) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
rep(k, 4) {
G[bx + DX[k] + L][by + DY[k] + L] = '.';
G[cx + DX[k] + L][cy + DY[k] + L] = '.';
}
auto [mx, my] = e1 ? path_ad[1] : path_ad[sz(path_ad) - 2];
for (auto [x, y] : path_ad) {
if (x == mx && y == my) continue;
rep(k, 4) {
G[x + DX[k] + L][y + DY[k] + L] = '#';
}
}
G[mx + L][my + L] = '.';
dist = solve_maze(G, bx + L, by + L);
if (dist[cx + L][cy + L] == INF) return vector<pii>();
if (rev2) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
x = cx, y = cy; vector<pii> path_bc{ {x,y} };
while (x != bx || y != by) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_bc.push_back({ x, y });
}
dump("path_bc:", path_bc);
if (rev2) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
auto [nx, ny] = e2 ? path_bc[1] : path_bc[sz(path_bc) - 2];
for (auto [x, y] : path_bc) {
if (x == nx && y == ny) continue;
rep(k, 4) {
G[x + DX[k] + L][y + DY[k] + L] = '#';
}
}
G[nx + L][ny + L] = '.';
dist = solve_maze(G, mx + L, my + L);
if (dist[lx + L][ly + L] == INF) return vector<pii>();
if (rev3) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
x = lx, y = ly; vector<pii> path_ml{ {x,y} };
while (x != mx || y != my) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_ml.push_back({ x, y });
}
dump("path_ml:", path_ml);
if (rev3) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
for (auto [x, y] : path_ml) {
if (x == lx && y == ly) continue;
rep(k, 4) {
G[x + DX[k] + L][y + DY[k] + L] = '#';
}
}
G[lx + L][ly + L] = '.';
dist = solve_maze(G, nx + L, ny + L);
if (dist[lx + L][ly + L] == INF) return vector<pii>();
if (rev4) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
x = lx, y = ly; vector<pii> path_nl{ {x,y} };
while (x != nx || y != ny) {
rep(k, 4) {
if (dist[x + DX[k] + L][y + DY[k] + L] == dist[x + L][y + L] - 1) {
x += DX[k];
y += DY[k];
break;
}
}
path_nl.push_back({ x, y });
}
dump("path_nl:", path_nl);
if (rev4) {
reverse(DX, DX + 4);
reverse(DY, DY + 4);
}
set<pii> walls;
for (auto [x, y] : path_ad) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_bc) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_ml) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_nl) {
rep(k, 4) walls.insert({ x + DX[k], y + DY[k] });
}
for (auto [x, y] : path_ad) {
walls.erase({ x, y });
}
for (auto [x, y] : path_bc) {
walls.erase({ x, y });
}
for (auto [x, y] : path_ml) {
walls.erase({ x, y });
}
for (auto [x, y] : path_nl) {
walls.erase({ x, y });
}
return vector<pii>(all(walls));
}
void Main() {
int ax, ay, bx, by, cx, cy, dx, dy;
cin >> ax >> ay >> bx >> by >> cx >> cy >> dx >> dy;
swap(bx, cx);
swap(by, cy);
if (abs(ax + ay + cx + cy) & 1) {
cout << -1 << "\n";
return;
}
rep(rev, 2) {
auto res = solveAC(ax, ay, bx, by, cx, cy, dx, dy, rev);
if (!res.empty()) {
cout << sz(res) << "\n";
for (auto [x, y] : res) cout << x << " " << y << "\n";
return;
}
}
rep(sx, 2) rep(sy, 2) rep(e1, 2) rep(e2, 2) rep(rev, 2) rep(rev2, 2) rep(rev3, 2) rep(rev4, 1) {
auto res = solveAD(ax, ay, bx, by, cx, cy, dx, dy,
rev, rev2, rev3, rev4, (sx ? 1 : -1) * 196, (sy ? 1 : -1) * 196, e1, e2);
if (!res.empty()) {
cout << sz(res) << "\n";
for (auto [x, y] : res) cout << x << " " << y << "\n";
return;
}
}
exit(-1);
cout << -1 << "\n";
}
int main() {
input_from_file("input.txt");
// output_to_file("output.txt");
int t = 1;
cin >> t; // マルチテストケースの場合
while (t--) {
dump("------------------------------");
Main();
}
}