Hướng dẫn cho Tam giác không vuông
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
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;
}
Bình luận
Mình làm sort 3 số tăng dần xong check a+b>c và aa + bb!=c*c vẫn AC nha. Ko cần bignum hay Hash gì cả. Nhưng các biến để kiểu unsigned long long là ok nha. Đọc sol các bạn thấy hơi bất ngờ ahihi.