Editorial for Thi thử Duyên hải 2021 - Lần 2 - Bài 3 - Tóm tắt


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.

Author: SPyofgame


~\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

Please read the guidelines before commenting.


There are no comments at the moment.