CodeChef - Chef and Triangles - かっつのメモ帳

問題のリンク

問題概要

内接円の半径がRとなるような、辺の長さが全て整数の三角形を全て求めよ。

制約

$1 \leqq R \leqq 100$

考察

内接円の半径と三角形の3辺の長さの関係を知りたい→面積についての等式を立てる

三角形の3辺の長さを $A \leqq B \leqq C$ とします。この時ヘロンの公式を用いると、

$(\frac{1}{2} R(A+B+C))^{2}=\frac{A+B+C}{2}(\frac{A+B+C}{2} -A)(\frac{A+B+C}{2} -B)(\frac{A+B+C}{2} -C)$

となり、X=A+B-C , Y=A+C-B , Z=B+C-A とおくと、仮定より $X \leqq Y \leqq Z$ であり次のように表せます。

$4R^{2}= \frac{XYZ}{X+Y+Z}$

先ほどの不等式を用いて評価してあげると、

$4R^{2}= \frac{XYZ}{X+Y+Z}\geqq \frac{XYZ}{Z+Z+Z} = \frac{XY}{3} \geqq \frac{X^{2}}{3}$

となり、Xの取りうる値が分かります。同様にXを固定した時のYの通りうる値も求めることが出来るのでこの範囲を全探索すれば良いです。

実装

#include <iostream>
#include <vector>
#include <algorithm>
#include <array>
#include <math.h>
using namespace std;
typedef long long int ll;

using Triangle=array<int,3>;

vector<Triangle> solve(int r){
    auto res=vector<Triangle>();
    for(int x=1;x<=2*r*sqrt(3);x++){
        for(int y=x;y<=12*r*r/x;y++){
            if(x*y-4*r*r==0)continue;
            if((4*r*r*(x+y))%(x*y-4*r*r))continue;
            int z=4*r*r*(x+y)/(x*y-4*r*r);
            if(y>z||x>z)continue;
            if((x+y)%2||(y+z)%2||(z+x)%2)continue;
            int a=(x+y)/2,b=(x+z)/2,c=(y+z)/2;
            res.push_back({a,b,c});
        }
    }
    sort(res.begin(),res.end());
    return res;
}

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    int r; cin >> r;
    auto res=solve(r);
    printf("%d\n",res.size());
    for(auto p:res){
        printf("%d %d %d\n",p[0],p[1],p[2]);
    }
}