はまやんはまやんはまやん

hamayanhamayan's blog

FindThePerfectTriangle [TopCoder SRM 738 Div1 Easy]

条件を満たす3頂点を答えよ

  • x,y座標が[0,3000]に収まる
  • できる三角形の外周がperimeterであり、面積がarea

解法

どのような三角形も回転や平行移動をすれば、(0,0)を通るようにできる。
なので、1つの頂点は(0,0)で他の2頂点を考えよう。
他の2頂点は外周が整数であるため、(0,0)からの長さも整数になる必要がある。
[0,3000]の範囲で(0,0)からの長さが整数となる点はそんなに多くない(10^4くらい)。
なので、これを全部探し、そのうち2つを、他の2頂点として採用できるか考える。

一辺がx軸、y軸に平行になると仮定するのは以下で落ちる。
area=252, perimeter=84のとき{0, 0, 16, 30, 28, 21}が答え。
ちなみに聞かれている三角形はヘロンの三角形と言う。

bool isSquare(ll n) {
    ll d = (ll)sqrt(n) - 1;
    while (d*d < n) ++d;
    return d * d == n;
}

struct FindThePerfectTriangle {
    vector <int> constructTriangle(int area, int perimeter) {
        vector<tuple<int, int, int>> v;
        rep(x, 0, 3001) rep(y, 0, 3001) {
            int d = x * x + y * y;
            if (isSquare(d)) {
                int dd = sqrt(d) + 0.1;
                v.push_back(make_tuple(x, y, dd));
            }
        }
        area *= 2;

        int n = v.size();

        rep(a, 0, n) rep(b, a + 1, n) {
            int ax, ay, ad, bx, by, bd;
            tie(ax, ay, ad) = v[a];
            tie(bx, by, bd) = v[b];

            if (perimeter <= ad + bd) continue;
            
            int are = abs(ax*by - ay * bx);
            if (are == area) {
                int dx = abs(ax - bx);
                int dy = abs(ay - by);
                int d = dx * dx + dy * dy;
                if (isSquare(d)) {
                    int dd = sqrt(d) + 0.1;
                    if (ad + bd + dd == perimeter) {
                        vector<int> ans;
                        ans.push_back(0);
                        ans.push_back(0);
                        ans.push_back(ax);
                        ans.push_back(ay);
                        ans.push_back(bx);
                        ans.push_back(by);
                        return ans;
                    }
                }
            }
        }

        return {};
    }
};