Editorial for Thi thử Duyên hải 2021 - Lần 2 - Bài 3 - Tóm tắt
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
~\color{orange}{\text{Hướng dẫn}}~
- Điều kiện dể 6 cạnh tạo thành hình tứ diện:
4 hình tam giác có các cạnh kề nhau
Thể tích hình tứ diện nguyên dương
~\color{goldenrod}{\text{Tiếp cận}}~
Gọi các cạnh hình tứ diện là ~AB,BC,CA,OA,OB,OC~, ta thử gán các gán giá trị cho các cạnh là các bộ 6 số có thể tạo từ dữ liệu nhập vào
Gọi ~f(a, b, c)~ là hàm kiểm tra xem 3 cạnh ~a, b, c~ có tạo ra được tam giác hay không
Các cạnh nguyên dương: ~a > 0~ và ~b > 0~ và ~c > 0~
Tổng hai cạnh lớn hơn cạnh còn lại: ~a + b > c~ và ~b + c > a~ và ~c + a > b~
- Gọi ~f(u, U, v, V, w, W)~ là hàm tính thể tích của hinh tứ diện, với ~(u, v, w)~ là bộ ba cạnh đáy, ~(U, V, W)~ là bộ ba cạnh trên, ~(U, u), (V, v), (W, w)~ là 3 cặp cạnh đối nhau
Áp dụng công thức Heron ta có ~V = \large{\frac{\normalsize{\sqrt{(w \times w + u \times u - V \times V) \times (v \times v + w \times w - U \times U) \times (u \times u + v \times v - W \times W) + 2 \times 2 \times u \times u \times v \times v \times w \times w - u \times u \times (v \times v + w \times w - U \times U) \times (v \times v + w \times w - U \times U) - v \times v \times (w \times w + u \times u - V \times V) \times (w \times w + u \times u - V \times V) - w \times w \times (u \times u + v \times v - W \times W) \times (u \times u + v \times v - W \times W)}}}{\normalsize{12}}}~
Vâng, công thức kinh dị lắm luôn, để cho tiện thì ta định nghĩa
- ~A^2 = A \times A~
- ~X = (w^2 + u^2 - V^2)~
- ~Y = (v^2 + w^2 - U^2)~
- ~Z = (u^2 + v^2 - W^2)~
- ~T = (u \times v \times w)~
Thì lúc này công thức trên là ~V = \Huge{\frac{\Large{\sqrt{X \times Y \times Z + 2^{\LARGE{2}} \times T^{\LARGE{2}} - u^{\LARGE{2}} \times Y^{\LARGE{2}} - v^{\Large{2}} \times X^{\Large{2}} - w^{\Large{2}} \times Z^{\Large{2}}}}}{\LARGE{12}}}~
~\color{purple}{\text{Độ phức tạp}}~
- Thử qua các bộ 6 cạnh mất ~O(6!)~ mỗi truy vấn
~\color{green}{\text{Code tham khảo }}~: Approach
~^{^{\color{purple}{\text{Độ phức tạp : }} O(6! \times Q)\ \color{purple}{\text{thời gian}}\ ||\ O(6)\ \color{purple}{\text{bộ nhớ}}}}~
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ldb;
///
/// *A
/// /|\
/// / | \
/// / d| \ a = BC
/// / | \ b = CA
/// / O \ c = AB
/// c / / \ \ b d = OA
/// / / \ \ e = OB
/// / / \ \ f = OC
/// / / e f \ \
/// // \\
/// / a \
/// *-----------------------*
/// B C
///
/// check if 3 edges form a triangle
bool isTri(ll a, ll b, ll c)
{
return (a + b > c) && (b + c > a) && (c + a > b);
}
/// Tetrahedron Volumn
ldb volumn(ll u, ll U, ll v, ll V, ll w, ll W)
{
ldb X = (w * w + u * u - V * V);
ldb Y = (v * v + w * w - U * U);
ldb Z = (u * u + v * v - W * W);
ldb T = (u * v * w);
return sqrt(X * Y * Z + 2 * 2 * T * T - u * u * Y * Y - v * v * X * X - w * w * Z * Z) / 12;
}
bool query()
{
ll x[6];
for (int i = 0; i < 6; ++i)
cin >> x[i];
sort(x, x + 6);
if (x[0] <= 0) return false;
do
{
ll BC = x[0];
ll CA = x[1];
ll AB = x[2];
ll OA = x[3];
ll OB = x[4];
ll OC = x[5];
bool ABC = isTri(BC, CA, AB);
bool OBC = isTri(BC, OB, OC);
bool OCA = isTri(CA, OC, OA);
bool OAB = isTri(AB, OA, OB);
ldb V_OABC = volumn(OA, BC, OB, CA, OC, AB);
if (ABC && OBC && OCA && OAB && V_OABC > 0) return true;
}
while (next_permutation(x, x + 6));
return false;
}
int main()
{
int q;
cin >> q;
while (q-->0) cout << (query() ? "Yes" : "No") << '\n';
return 0;
}
Comments