結果

問題 No.132 点と平面との距離
ユーザー はむ吉🐹はむ吉🐹
提出日時 2016-08-26 18:54:24
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,667 ms / 5,000 ms
コード長 3,124 bytes
コンパイル時間 2,333 ms
コンパイル使用メモリ 92,228 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-11-08 05:25:44
合計ジャッジ時間 6,483 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 100 ms
5,248 KB
testcase_01 AC 791 ms
5,248 KB
testcase_02 AC 2,667 ms
5,248 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cassert>
#include <ciso646>
#include <cstdlib>
#include <iomanip>
#include <ios>
#include <iostream>
#include <type_traits>
#include <valarray>
#include <vector>


constexpr int DIGITS = 12;


template <typename T> using RowVector = std::valarray<T>;
template <typename T> using Matrix = std::valarray<RowVector<T>>;


template <typename T> T determinant(Matrix<T> a) {
    static_assert(std::is_floating_point<T>() == true,
        "Use floating point numbers");
    auto n = a.size();
    assert(n > 0 and a[0].size() == n);
    for (decltype(n) i = 0; i < n; i++)
    {
        for (decltype(n) j = 0; j < n; j++)
        {
            if (i < j)
            {
                auto b = a[j][i] / a[i][i];
                for (decltype(n) k = 0; k < n; k++)
                {
                    a[j][k] -= a[i][k] * b;
                }
            }
        }
    }
    T d = 1;
    for (decltype(n) i = 0; i < n; i++)
    {
        d *= a[i][i];
    }
    return d;
}


template <typename T> T norm(RowVector<T> v) {
    static_assert(std::is_floating_point<T>() == true,
        "Use floating point numbers");
    auto u = v.apply([](T x) {return x * x; });
    return std::sqrt(u.sum());
}


template <typename T> RowVector<T> cross_product3(RowVector<T> u, RowVector<T> v) {
    assert(u.size() == 3 and v.size() == 3);
    auto m1 = u[1] * v[2] - u[2] * v[1];
    auto m2 = u[2] * v[0] - u[0] * v[2];
    auto m3 = u[0] * v[1] - u[1] * v[0];
    RowVector<T> cp = { m1, m2, m3 };
    return cp;
}


template <typename T> T volume_of_trigonal_pyramid(RowVector<T> p,
    RowVector<T> q1, RowVector<T> q2, RowVector<T> q3) {
    auto v1 = q1 - p;
    auto v2 = q2 - p;
    auto v3 = q3 - p;
    Matrix<T> a = { v1, v2, v3 };
    return std::abs(determinant(a) / 6);
}


template <typename T> T area_of_triangle(RowVector<T> q1,
    RowVector<T> q2, RowVector<T> q3) {
    auto v2 = q2 - q1;
    auto v3 = q3 - q1;
    return norm<T>(cross_product3<T>(v2, v3)) / 2;
}


template <typename T> T dist(RowVector<T> p,
    RowVector<T> q1, RowVector<T> q2, RowVector<T> q3) {
    auto v = volume_of_trigonal_pyramid(p, q1, q2, q3);
    auto s = area_of_triangle(q1, q2, q3);
    return v * 3 / s;
}


template <typename T> T sum_of_dist(RowVector<T> p,
    std::vector<RowVector<T>> qs){
    auto n = qs.size();
    T d = 0;
    for (decltype(n) i = 0; i < n; i++)
    {
        for (decltype(n) j = i + 1; j < n; j++)
        {
            for (decltype(n) k = j + 1; k < n; k++)
            {
                d += dist(p, qs[i], qs[j], qs[k]);
            }
        }
    }
    return d;
}


int main() {
    std::cin.tie(nullptr);
    std::ios::sync_with_stdio(false);
    std::cout << std::setprecision(DIGITS) << std::fixed;
    int n;
    std::cin >> n;
    RowVector<double> p(3);
    std::cin >> p[0] >> p[1] >> p[2];
    std::vector<RowVector<double>> qs;
    for (decltype(n) i = 0; i < n; i++)
    {
        RowVector<double> q(3);
        std::cin >> q[0] >> q[1] >> q[2];
        qs.push_back(q);
    }
    auto ans = sum_of_dist(p, qs);
    std::cout << ans << std::endl;
    return EXIT_SUCCESS;
}
0