Editorial for Tam giác không vuông

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Spoiler Alert

Hint 1

  • Tìm điều kiện tam giác và loại bỏ điều kiện để nó vuông, từ đó suy ra kết quả

Điều kiện độ dài các cạnh: \((a > 0) \ \&\ (b > 0) \ \&\ (c > 0)\)

Điều kiện để tạo tam giác: \((a + b > c) \ \&\ (b + c > a) \ \&\ (c + a > b)\)

Điều kiện để tam giác vuông: \((a^2 + b^2 = c^2) || (b^2 + c^2 = a^2) || (c^2 + a^2 == b^2)\)

Hint 2

  • Ta cũng có thể sắp xếp các cạnh thành \(a \leq b \leq c\) để có công thức toán học gọn hơn

Điều kiện độ dài các cạnh: \((a > 0)\) (cạnh bé nhất dương)

Điều kiện để tạo tam giác: \((a + b > c)\) (tổng hai cạnh bé lớn hơn cạnh lớn nhất)

Điều kiện để tam giác vuông: \((a^2 + b^2 = c^2)\) (tổng bình phương hai cạnh góc vuông bằng cạnh huyền)

Hint 3

  • Ngoài bignum để nhân hai số lớn, ta có thể chuyển đổi toán học

\(a ^ 2 + b ^ 2 = c ^ 2 \Leftrightarrow \frac{a}{c - b} = \frac{c + b}{a}\)

Đưa hai phân số về tối giản, ta kiểm tra tử với từ, mẫu với mẫu là xong

Reference AC code | \(O(\log max\_val)\) time | \(O(1)\) auxiliary space | Math

C++
/// check a * a + b * b = c * c <=> a / (c - b) = (c + b) / a
inline bool isPythagorean(ll a, ll b, ll c) {
    pair<ll, ll> n1 = mp(a, c - b);     /// phan so thu nhat
    pair<ll, ll> n2 = mp(b + c, a);     /// phan so thu hai
    ll d1 = gcd(n1.first, n1.second);   /// ucln p/s thu nhat
    ll d2 = gcd(n2.first, n2.second);   /// ucln p/s thu hai
    n1.first /= d1;    n1.second /= d1; /// toi gian p/s thu nhat
    n2.first /= d2;    n2.second /= d2; /// toi gian p/s thu hai
    return (n1.first == n2.first && n1.second == n2.second); /// kiem tra hai p/s bang nhau
}

/// Voi moi truy van
int query()
{
    ll a, b, c;
    cin >> a >> b >> c;

    /// sort a < b < c  
    if (a > b) swap(a, b);
    if (a > c) swap(a, c);
    if (b > c) swap(b, c);

    if (a <= 0 || a + b <= c)   return cout << "NO\n", 0; /// (a, b, c) khong phai cac canh tam giac
    if (isPythagorean(a, b, c)) return cout << "NO\n", 0; /// (a, b, c) la cac canh tam giac vuong

    return cout << "YES\n", 0; /// (a, b, c) thoa man
}

Another Approach

  • Sài Hash + nhân ấn độ, bạn có thể kiểm tra trong \(O(1)\)

Reference AC code | \(O(\log max\_val)\) time | \(O(1)\) auxiliary space | Math, Hash

C++
/// cac so modulo nguyen to 18 chu so 
vector<ll> modulo = {
    100055128505716009,100707069199565201,101210328665281103,103509442668384329,103901850164540539,
    107164751690556253,108903531991843321,110356113559705927,110437474552301887,111991323706419863
};

/// nhan an do: (a * b) % m
inline ll mulMOD(ll a, ll b, ll m = MOD) {
    ll res = 0;
    for (a %= m, b %= m; b > 0; a <<= 1, b >>= 1) {
        if (a >= m) a -= m;
        if (b & 1) { res += a; if (res >= m) res -= m; }
    }
    return res;
}

/// ham kiem tra: check a * a + b * b = c * c <=> a / (c - b) = (c + b) / a
inline bool isPythagorean(ll a, ll b, ll c) {
    for (ll &m : modulo)
        if ((mulMOD(a, a, m) + mulMOD(b, b, m)) % m != mulMOD(c, c, m))
            return false;

    return true;
}

Comments

There are no comments at the moment.