algoNote

プログラミング関連

SRM738 easy - FindThePerfectTriangle

System Testで落ちて0ptでした...

問題概要

三角形の周囲の長さ(perimeter)と面積(area)が与えられる。
周囲の長さ、面積が与えられたものに一致し、各頂点の座標が整数となるような三角形が存在するか判定し、存在するなら頂点の座標を返せ。(複数存在するならどれでもいい)

制約

  • perimeter, area は整数
  •  1 \leq area  \leq 10^6
  •  1 \leq perimeter  \leq 1000
  •  0 \leq 頂点の座標の値  \leq 3000

解法

1点を原点に固定して残りの2点の座標を探索します。

2点の座標を(x1, y1), (x2, y2)とすると、面積は area = \frac{1}{2} |x1y2 - x2y1|になります。
変形して area \times 2 = |x1y2 - x2y1|
このうちx1y2を固定することを考えます。答えとなりうる三角形の一辺の長さの値の範囲を考えると、P/2未満であることが必要です。(正の面積を持つので当たり前ですが)
よって各座標値の絶対値はP/2以下であることが分かるので、まずx1を500以下の範囲で決めて、y2をP-x1の範囲で決めます。

絶対値を外す時にx1y2, x2y1の大小によって場合分けが必要ですが、今回は条件を満たす物を1つ出力すれば良いので、x1y2 > x2y1としてしまって問題ありません。
よって、x2y1 = x1y2 - area * 2と決まります。

あとは、符号に注意しながらx2y1を約数に分割してx2,y1を決め、条件を満たすかを試せばよいです。

コード

int isqrt[2000006];

struct FindThePerfectTriangle {
    int P;
    int A;

    inline bool check_sq(int s) {
        int sq = isqrt[s];
        return (sq * sq == s);
    }
    
    inline bool check(int x1, int x2, int y1, int y2) {
        if (abs(x1) > 600 || abs(x2) > 600 || abs(y1) > 600 || abs(y2) > 600) return false;

        int sum1 = x1 * x1 + y1 * y1;
        if (!check_sq(sum1)) {
            return false;
        }
        
        int sum2 = x2 * x2 + y2 * y2;
        if (!check_sq(sum2)) {
            return false;
        }

        int sum3 = (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
        if (!check_sq(sum3)) {
            return false;
        }

        return (isqrt[sum1] + isqrt[sum2] + isqrt[sum3] == P);
    }

    inline int sign(int x) {
        if (x < 0) return -1;
        return 1;
    }

    vector<int> constructTriangle(int area, int perimeter) {
        for (int i = 0; i * i <= 2000000; i++) isqrt[i * i] = i;

        P = perimeter;
        A = area;

        REP(x1, 501) {
            REP(y2, P - x1) {
                int x2y1 = x1 * y2 - area * 2;

                for (int i = 1; i * i <= abs(x2y1); i++) {
                    if (x2y1 % i == 0) {
                        int x2, y1;

                        for (auto sign1 : {-1, 1}) {
                            for (auto sign2 : {-1, 1}) {
                                if (sign1 * sign2 != sign(x2y1)) continue;

                                x2 = sign1 * i;
                                y1 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};

                                y1 = sign1 * i;
                                x2 = sign2 * abs(x2y1) / i;
                                if (check(x1, x2, y1, y2))
                                    return {x1 + 1500, y1 + 1500, x2 + 1500, y2 + 1500, 1500, 1500};
                            }
                        }
                    }
                }
            }
        }

        return {};
    }
};

TLEギリギリだったので少々強引な解な気もします…