条件を満たす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 {}; } };