結果

問題 No.132 点と平面との距離
ユーザー はむ吉🐹はむ吉🐹
提出日時 2017-10-09 19:08:28
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 671 ms / 5,000 ms
コード長 1,825 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,560 KB
実行使用メモリ 77,568 KB
最終ジャッジ日時 2024-04-28 14:24:23
合計ジャッジ時間 1,879 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 106 ms
76,416 KB
testcase_01 AC 254 ms
76,672 KB
testcase_02 AC 671 ms
77,568 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#!/usr/bin/env pypy3

import itertools
import math

NUM_AXES = 3


def compute_sum_of_dist(n, ps):
    # psを破壊的に変更
    for i, j in itertools.product(range(1, n), range(NUM_AXES)):
        # P (Q_0) が原点になるように移動
        ps[i][j] -= ps[0][j]
    for j in range(NUM_AXES):
        ps[0][j] = 0.0
    # 二点間距離を前計算
    dist = [[0.0 for _ in range(n)] for _ in range(n)]
    for p1, p2 in itertools.combinations(range(n), 2):
        dist[p1][p2] = math.sqrt(sum((ps[p1][a] - ps[p2][a]) ** 2
                                     for a in range(NUM_AXES)))
        dist[p2][p1] = dist[p1][p2]

    # 三角形の面積
    def area_of_triangle(p1, p2, p3):
        a = dist[p1][p2]
        b = dist[p2][p3]
        c = dist[p3][p1]
        s = (a + b + c) / 2.0
        return math.sqrt(s * (s - a) * (s - b) * (s - c))

    # 四面体の体積
    def volume_of_tetrahedron(p1, p2, p3):
        x1, y1, z1 = ps[p1]
        x2, y2, z2 = ps[p2]
        x3, y3, z3 = ps[p3]
        vol = y1 * z2 * x3 + z1 * x2 * y3 + x1 * y2 * z3
        vol = vol - z1 * y2 * x3 - x1 * z2 * y3 - y1 * x2 * z3
        vol = abs(vol) / 6.0
        return vol

    # 高さ
    def height(p1, p2, p3):
        vol = volume_of_tetrahedron(p1, p2, p3)
        area = area_of_triangle(p1, p2, p3)
        height = vol / area * 3
        return height

    g = itertools.combinations(range(1, n), 3)
    res = sum(height(*qs) for qs in g)
    return res


def main():
    n = int(input()) + 1
    ps = [[0.0 for _ in range(NUM_AXES)] for _ in range(n)]
    for i in range(n):
        ws = tuple(float(w) for w in input().split())
        for j in range(NUM_AXES):
            ps[i][j] = ws[j]
    res = compute_sum_of_dist(n, ps)
    print("{:.12f}".format(res))


if __name__ == '__main__':
    main()
0