Document

Triangles
問題作成:荒木
解答作成:荒木、林崎
英訳:荒木、吉野
解説:荒木
問題の説明
• 一辺の長さが1のn枚
の正三角形を、重心を
そろえて重ね、重心を
中心として上から順に、
直上のものから360/n
度反時計回りにずらし
ていった時、それを上
から見たときの面積を
求めよ。
• 右はn=4の例。
解法
• 先に結論を言うと、右
図の青色の部分の面
積を求め、nが3の倍数
の時は2n倍、nが3の
倍数以外の時は6n倍
すればよい。
補題1
• 右図の赤線のように、
隣り合う三角形の角の
間に他の三角形の辺
が入ることは無い。
補題1の証明①
• A,Bが隣り合う二点とす
る。線分ACをOを中心
として線分DBに重なる
まで反時計回りに回転
した時に、線分ACがE
の右側に来ないことを
示せばよい。
補題1の証明②
• 線分ACを反時計周り
にα-θ回転した線分A’C’
に重なる直線は、
cos(α-60°)x+sin(α60°)y-1/2√3=0
• y=0とすると
x=1/(2√3cos(α-60°))
• αについて微分すると、
x=sin(α-60°)
/(12cos^2(α-60°)
補題1の証明③
• 増減表を書くと0°<θ<=60°より
α
θ
ｘ'
-
x
Eのx座標
60°
-
0
1/2√3
120°-θ
+
+
Eのx座標
• よって、交点のx座標がEより右に来ることはない。
補題2
• 右図の青い部分は、n
が3の倍数の時はn個、
nが3の倍数でない時は
3n個出来る。
補題2の証明①
• 青い部分の角度αは0
を基点とすると、0,
360/n, 360*2/n, …
360*(n-1)/n, 120,
360/n+120,
360*2/n+120, …
360*(n-1)/n+120, 240,
360/n+240,
360*2/n+240, …
360*(n-1)/n+240
補題2の証明②
• nが3の倍数だと、360*(l+2m)/3m,
360*(l+m)/3m+120, 360*l/3m+240が重なる。
• nが3の倍数以外だと,360*k/nが120に等しく
なるようなkが存在しないので、角は重ならな
い。
青い三角形の面積の求め方
• nが3の倍数
…θ=180°/n
• nが3の倍数でない
…θ=60°/n
• h*√3 + h/tanθ=1/ √3
• h= 1/√3(√3+1/tanθ)
• 面積=1/6(√3+1/tanθ)
h
θ
1/√3
30°
デバッグヒント
• n→∞の時、求める面積はπ/3に収束する。
実行時間と行数
• 0.1秒程度
• 20～40行程度
– 式さえ立てばコードは短い
コンテストの結果
• Submit:11
• Accept:9(first accept:__________12分)
• 全チームacceptおめでとうございます。特に
__________はすごかったと思います。
おまけ
• 134 Bytes
• #include<stdio.h>
main(n){for(freopen("E.txt","r"
,stdin);scanf("%d",&n),n;printf
("%lf\n",n/(1/tan(1.047198/n)+s
qrt(3))))n%3||(n/=3);}

Download Report