SRM 645 div1 med: ArmyTeleportation

途中までは思いついたけど,そこまでだった。

問題:TopCoder Statistics - Problem Statement

解法:まず1次元の場合で問題にあるような対称移動をすることを考える。点xにいるときにAiに対して対称移動してからAjに対して対称移動した時の座標は

となる。すなわち,点xの位置にかかわらず点xから2*(Aj-Ai)だけ平行移動したことになる。これを2次元にも拡張して,2点があったら2回分移動を消費して平行移動することができると考えることができる。

ところで,軍隊の移動の仕方について考察すると,軍隊は対称移動を利用して偶数回移動するか,奇数回移動するかのいずれかである。偶数回移動する場合は,それらを2回区切りで考えることによって,すべて平行移動することで移動を実現したと考えることができる。一方,奇数回移動する場合は,最初に一回対称移動して,その後平行移動をすることで実現したと考えることができる。
以上により,可能性としては,
①軍隊を平行移動させて目的の場所に移動させる
②3つあるうちの1つの場所について対称移動してから目的の場所に平行移動させる
のいずれかで目的地に行くことになる。

軍隊の場所と目的地の場所について,座標ソートをすると,それぞれの軍隊がどの目的地と対応するかがわかる(もし軍隊と目的地で対応しないのがあったらそれは条件を満たさない)。なのであとは平行移動することで座標のズレdx, dyを補完できるかを考えれば良い。

平行移動できる候補としては(は2次元ベクトルとする),
の3つがあるが,
であるので,結局を用いてdx,dyを補完できるかを考えれば良い。
行列]が逆行列を持つときは単純に逆行列をかけて整数解が存在するかを調べれば良い。逆行列を持たない時は,のx座標が0の時(この時のx座標が0であることは保証されている),y座標が0(x座標と同様)の時,その他の時について,方程式が整数解を(p,q)を持つのはgcd(x,y)がdの約数の時であるということを用いて解が存在するかを考えれば良い。
以下ソースコード

struct Point {
    ll y;
    ll x;
    Point() {}
    Point(int y, int x) : y(y), x(x) {}
    bool operator<(const Point& rhs) const {
        if (y != rhs.y) return y < rhs.y;
        return x < rhs.x;
    }
};

class ArmyTeleportation {
public:
    string ifPossible(vector <int> x1, vector <int> y1, vector <int> x2, vector <int> y2, vector <int> xt, vector <int> yt) {
        int n = x1.size();
        vector<Point> p2(n);
        Point v1, v2;
        v1.x = 2*(xt[2]-xt[0]), v1.y = 2*(yt[2]-yt[0]);
        v2.x = 2*(xt[2]-xt[1]), v2.y = 2*(yt[2]-yt[1]);
        for (int i = 0; i < n; i++) {
            p2[i].x = x2[i];
            p2[i].y = y2[i];
        }
        sort(p2.begin(), p2.end());
        for (int i = 0; i < 4; i++) {
            vector<Point> ps(n);
            if (i == 3) {
                for (int j = 0; j < n; j++) {
                    ps[j].x = x1[j];
                    ps[j].y = y1[j];
                }
            } else {
                for (int j = 0; j < n; j++) {
                    ps[j].x = 2*xt[i]-x1[j];
                    ps[j].y = 2*yt[i]-y1[j];
                }
            }
            sort(ps.begin(), ps.end());
            ll dx = p2[0].x - ps[0].x;
            ll dy = p2[0].y - ps[0].y;
            bool ng = false;
            for (int j = 0; j < n; j++) {
                if (p2[j].x - ps[j].x != dx || p2[j].y - ps[j].y != dy) {
                    ng = true;
                    break;
                }
            }
            if (ng) continue;
            ll tmp = v1.x * v2.y - v2.x * v1.y;
            if (tmp != 0) {
                if ((v2.y*dx-v2.x*dy) % tmp == 0 && (-v1.y*dx + v1.x*dy) % tmp == 0) return "possible";
            } else {
                if (v1.x == 0) {
                    if (dx == 0 && dy % __gcd(v1.y, v2.y) == 0) return "possible";
                }
                if (v1.y == 0) {
                    if (dy == 0 && dx % __gcd(v1.x, v2.x) == 0) return "possible";
                }
                if (dx*v2.y == dy*v2.x) {
                    ll gx = __gcd(v1.x, v2.x);
                    if (dx % gx == 0) return "possible";
                }
            }
        }
        return "impossible";
    }
};