Day 2 Problem C
Tetrahedra
ACM/ICPC
Japanese Alumni Group
講評担当: 吉野
Rev. 1.1
問題概要
• 長さ整数の辺がいくつか与えられるので、
適当に選択して四面体を作る
– 辺は 15 本まで、長さはたかだか 100[cm]
– 辺を 2 本以上つないだりしてはいけないという
制約がある
• この条件のもとで作れる最大の四面体の
体積を求めよ
– 誤差は 10-6 以内
Submit 状況
• Total 9 submits (コンテスト時間中)
– うち 4 チーム accepted
– First acceptance: 137 min. (CLAGGANO)
– トライしてくれたところはみんな解けました
• kitsune-, CLAGGANO, clax, echizen.com
解法
• 辺を 6 本選んで四面体をつくれるか判断し、作れる
場合は体積を計算
– 辺をつないだりしてはいけないので、これでよい
– 高々 15P6 = 3,603,600 なので、全探索で OK
• 底面の選択で明らかな重複を省けるので 15P6÷3! が簡単に
思いつくでしょう
• また、辺の長さしか問題にしないので、数だけ数える等でさらに
高速化できます (やらなくても通るようにはなっている)
• 本質は四面体の体積を求める式を立てるところだけ
– 上位チームはみんな解けてほしいなあ
たとえばこー書く
double volume = 0.0;
vector<bool> used(prob.size(), false);
nC3
for(int i1 = 0; i1 < prob.size(); i1++)
for(int i2 = i1 + 1; i2 < prob.size(); i2++)
for(int i3 = i2 + 1; i3 < prob.size(); i3++) {
if(! check_triangle(prob[i1], prob[i2], prob[i3])) continue;
used[i1] = used[i2] = used[i3] = true;
for(int h1 = 0; h1 < prob.size(); h1++) {
if(used[h1]) continue; used[h1] = true;
for(int h2 = 0; h2 < prob.size(); h2++) {
if(used[h2]) continue; used[h2] = true;
n-3 3
for(int h3 = 0; h3 < prob.size(); h3++) {
if(used[h3]) continue;
if(! check_triangle(prob[i1], prob[h1], prob[h2]) || ...)
continue;
const double v = volume(prob[h1], prob[h2], prob[h3], ...);
if(v > volume) volume = v;
}
used[h2] = false;
}
used[h1] = false;
}
used[i1] = used[i2] = used[i3] = false;
}
return volume;
P
四面体ってどんな形だっけ
• 各面は三角形なので、辺の長さが決まれば
形は一意に決まる
辺は 6 本必要
各面は必ず
三角形
Phase 1:
四面体になるかどうか判定
• 4 面それぞれについて、与えられた 3 辺が
三角形を作るかどうかを判定すればよい
– (3 本のうち最長のもの) < (残りの 2 本の和)
• 今回の場合入力が整数なので、誤差等は考えなくて
よい
• また、面積 = 0 になる場合は切っておきたいので
等号は入らない (後述)
Phase 2:
四面体の体積を求める
• 基本的には中学～高校の幾何を駆使すれば
紙の上の計算だけで求まる
– 余弦定理 (または 2 次方程式を解く)
– ピタゴラスの定理
– ヘロンの公式
– 一般的な錐体の体積の公式
四面体の体積 (1)
• 基本は三角錘と考えて、錐体の体積の公式
– S = 底面の面積, h = 高さ
• ただし高さが簡単にはわからない
– 底面は三角形なので、面積は辺の長さから
ヘロンの公式で求まる
b
a
c
四面体の体積 (2)
• とりあえず一辺を x 軸に固定して、底面に垂
直な方向から見ると…
(x0, y0)
b
O
c
(a,0)
– 適当に方程式をとく or 余弦定理で出ます
余弦定理
• 三角形の 3 辺の長さから内角の cos を
求める
A
c
b
θ
a
– 上の頂点 A の座標は
⇒ 先ほど出てきた式
四面体の体積 (3)
• 手前にある頂点を底面に投影した位置(底面
に下ろした垂線の足の位置)を求める
(x0, y0)
(x1, y1)
l3
b
l2
O
l1
展開図を”起こす”
ときに頂点の通る
(a,0)
軌跡(の延長)
– 点線は底面の各辺に垂直
– y0 = 0 のケースは三角形判定で切られている
ため、NaN とかは出なくて ”安全”
展開図から立体へ
面の回転軸
四面体の体積 (4)
• あとはピタゴラスの定理で高さを求める
l2
O
–
h
s
A = (a, 0)
• b ≦ s の場合には四面体にならないので注意
• 鈍角(足が底面の外にある場合)の場合わけは不要
まとめ
• みなさん、高校の数学を忘れていませんか？
• 3 次元幾何が出てくるからと問題を切って
いませんか？
そのまま放っておくと
大変なことになりますよ
TM
© Copyright 2024 ExpyDoc
