2024年度「アルゴリズムとデータ構造」のページ

2024年10月7日出題

1. ユークリッド平面上に三角形 $ABC$ を固定する。平面上の点 $X$ が実数の三つ組 $\lambda ,\mu ,\nu$ を使って位置ベクトルに関して $(\lambda +\mu +\nu )X=\lambda A+\mu B+\nu C$ と表せるとき、 $X=\lambda :\mu :\nu$ と書く。

   成分で書き下すと、 $$A=(x_A,y_A),B=(x_B,y_B),C=(x_C,y_C),X=\lambda :\mu :\nu$$ のとき $$X=(\frac{\lambda x_A+\mu x_B+\nu x_C}{\lambda +\mu +\nu },\frac{\lambda y_A+\mu y_B+\nu y_C}{\lambda +\mu +\nu })$$ である。

   三角形の中点三角形、反中点三角形、内心三角形、傍心三角形、ジェルゴンヌ三角形、ナーゲル三角形は、以下のように定義される。

   元の三角形を $ABC$ とし、作られる三角形を $A\prime B\prime C\prime$ とする。 辺 $BC$, $CA$, $AB$ の長さを、それぞれ、 $a$, $b$, $c$ と書く。

   中点三角形 (medial triangle)

   元の三角形の辺の中点を結ぶ三角形 $$A\prime =0:1:1,B\prime =1:0:1,C\prime =1:1:0$$

   反中点三角形 (anticomplementary triangle)

   元の三角形の頂点を通り対辺に平行な直線から構成される三角形 $$A\prime =\mathrm{-1}:1:1,B\prime =1:\mathrm{-1}:1,C\prime =1:1:\mathrm{-1}$$

   内心三角形 (incentral triangle)

   元の三角形の角の二等分線と対辺の交点を結ぶ三角形 $$A\prime =0:b:c,B\prime =a:0:c,C\prime =a:b:0$$

   傍心三角形 (excentral triangle)

   元の三角形の傍心を結ぶ三角形 $$A\prime =-a:b:c,B\prime =a:-b:c,C\prime =a:b:-c$$

   ジェルゴンヌ三角形 (Gergonne triangle)

   元の三角形の内接円と辺の接点を結ぶ三角形 $$A\prime =0:(a+b-c):(a-b+c),B\prime =(a+b-c):0:(-a+b+c),C\prime =(a-b+c):(-a+b+c):0$$

   ナーゲル三角形 (Nagel triangle)

   元の三角形の傍接円と対応する辺の接点を結ぶ三角形 $$A\prime =0:(a-b+c):(a+b-c),B\prime =(-a+b+c):0:(a+b-c),C\prime =(-a+b+c):(a-b+c):0$$

   1. 三角形の各頂点の座標を入力し、以下の三角形の各頂点の座標をすべて出力するプログラムを書け。入出力の書式は各自で決め、書式を記載した取扱説明書を添付すること。

      1. 中点三角形
      2. 反中点三角形
      3. 内心三角形
      4. 傍心三角形
      5. ジェルゴンヌ三角形
      6. ナーゲル三角形
      7. 中点三角形の中点三角形
      8. 中点三角形の反中点三角形
      9. 中点三角形の内心三角形
      10. 中点三角形の傍心三角形
      11. 中点三角形のジェルゴンヌ三角形
      12. 中点三角形のナーゲル三角形
      13. 反中点三角形の中点三角形
      14. 反中点三角形の反中点三角形
      15. 反中点三角形の内心三角形
      16. 反中点三角形の傍心三角形
      17. 反中点三角形のジェルゴンヌ三角形
      18. 反中点三角形のナーゲル三角形
      19. 内心三角形の中点三角形
      20. 内心三角形の反中点三角形
      21. 内心三角形の内心三角形
      22. 内心三角形の傍心三角形
      23. 内心三角形のジェルゴンヌ三角形
      24. 内心三角形のナーゲル三角形
      25. 傍心三角形の中点三角形
      26. 傍心三角形の反中点三角形
      27. 傍心三角形の内心三角形
      28. 傍心三角形の傍心三角形
      29. 傍心三角形のジェルゴンヌ三角形
      30. 傍心三角形のナーゲル三角形
      31. ジェルゴンヌ三角形の中点三角形
      32. ジェルゴンヌ三角形の反中点三角形
      33. ジェルゴンヌ三角形の内心三角形
      34. ジェルゴンヌ三角形の傍心三角形
      35. ジェルゴンヌ三角形のジェルゴンヌ三角形
      36. ジェルゴンヌ三角形のナーゲル三角形
      37. ナーゲル三角形の中点三角形
      38. ナーゲル三角形の反中点三角形
      39. ナーゲル三角形の内心三角形
      40. ナーゲル三角形の傍心三角形
      41. ナーゲル三角形のジェルゴンヌ三角形
      42. ナーゲル三角形のナーゲル三角形
      43. 中点三角形の中点三角形の中点三角形
      44. 中点三角形の中点三角形の反中点三角形
      45. 中点三角形の中点三角形の内心三角形
      46. 中点三角形の中点三角形の傍心三角形
      47. 中点三角形の中点三角形のジェルゴンヌ三角形
      48. 中点三角形の中点三角形のナーゲル三角形
      49. 中点三角形の反中点三角形の中点三角形
      50. 中点三角形の反中点三角形の反中点三角形
      51. 中点三角形の反中点三角形の内心三角形
      52. 中点三角形の反中点三角形の傍心三角形
      53. 中点三角形の反中点三角形のジェルゴンヌ三角形
      54. 中点三角形の反中点三角形のナーゲル三角形
      55. 中点三角形の内心三角形の中点三角形
      56. 中点三角形の内心三角形の反中点三角形
      57. 中点三角形の内心三角形の内心三角形
      58. 中点三角形の内心三角形の傍心三角形
      59. 中点三角形の内心三角形のジェルゴンヌ三角形
      60. 中点三角形の内心三角形のナーゲル三角形
      61. 中点三角形の傍心三角形の中点三角形
      62. 中点三角形の傍心三角形の反中点三角形
      63. 中点三角形の傍心三角形の内心三角形
      64. 中点三角形の傍心三角形の傍心三角形
      65. 中点三角形の傍心三角形のジェルゴンヌ三角形
      66. 中点三角形の傍心三角形のナーゲル三角形
      67. 中点三角形のジェルゴンヌ三角形の中点三角形
      68. 中点三角形のジェルゴンヌ三角形の反中点三角形
      69. 中点三角形のジェルゴンヌ三角形の内心三角形
      70. 中点三角形のジェルゴンヌ三角形の傍心三角形
      71. 中点三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      72. 中点三角形のジェルゴンヌ三角形のナーゲル三角形
      73. 中点三角形のナーゲル三角形の中点三角形
      74. 中点三角形のナーゲル三角形の反中点三角形
      75. 中点三角形のナーゲル三角形の内心三角形
      76. 中点三角形のナーゲル三角形の傍心三角形
      77. 中点三角形のナーゲル三角形のジェルゴンヌ三角形
      78. 中点三角形のナーゲル三角形のナーゲル三角形
      79. 反中点三角形の中点三角形の中点三角形
      80. 反中点三角形の中点三角形の反中点三角形
      81. 反中点三角形の中点三角形の内心三角形
      82. 反中点三角形の中点三角形の傍心三角形
      83. 反中点三角形の中点三角形のジェルゴンヌ三角形
      84. 反中点三角形の中点三角形のナーゲル三角形
      85. 反中点三角形の反中点三角形の中点三角形
      86. 反中点三角形の反中点三角形の反中点三角形
      87. 反中点三角形の反中点三角形の内心三角形
      88. 反中点三角形の反中点三角形の傍心三角形
      89. 反中点三角形の反中点三角形のジェルゴンヌ三角形
      90. 反中点三角形の反中点三角形のナーゲル三角形
      91. 反中点三角形の内心三角形の中点三角形
      92. 反中点三角形の内心三角形の反中点三角形
      93. 反中点三角形の内心三角形の内心三角形
      94. 反中点三角形の内心三角形の傍心三角形
      95. 反中点三角形の内心三角形のジェルゴンヌ三角形
      96. 反中点三角形の内心三角形のナーゲル三角形
      97. 反中点三角形の傍心三角形の中点三角形
      98. 反中点三角形の傍心三角形の反中点三角形
      99. 反中点三角形の傍心三角形の内心三角形
      100. 反中点三角形の傍心三角形の傍心三角形
      101. 反中点三角形の傍心三角形のジェルゴンヌ三角形
      102. 反中点三角形の傍心三角形のナーゲル三角形
      103. 反中点三角形のジェルゴンヌ三角形の中点三角形
      104. 反中点三角形のジェルゴンヌ三角形の反中点三角形
      105. 反中点三角形のジェルゴンヌ三角形の内心三角形
      106. 反中点三角形のジェルゴンヌ三角形の傍心三角形
      107. 反中点三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      108. 反中点三角形のジェルゴンヌ三角形のナーゲル三角形
      109. 反中点三角形のナーゲル三角形の中点三角形
      110. 反中点三角形のナーゲル三角形の反中点三角形
      111. 反中点三角形のナーゲル三角形の内心三角形
      112. 反中点三角形のナーゲル三角形の傍心三角形
      113. 反中点三角形のナーゲル三角形のジェルゴンヌ三角形
      114. 反中点三角形のナーゲル三角形のナーゲル三角形
      115. 内心三角形の中点三角形の中点三角形
      116. 内心三角形の中点三角形の反中点三角形
      117. 内心三角形の中点三角形の内心三角形
      118. 内心三角形の中点三角形の傍心三角形
      119. 内心三角形の中点三角形のジェルゴンヌ三角形
      120. 内心三角形の中点三角形のナーゲル三角形
      121. 内心三角形の反中点三角形の中点三角形
      122. 内心三角形の反中点三角形の反中点三角形
      123. 内心三角形の反中点三角形の内心三角形
      124. 内心三角形の反中点三角形の傍心三角形
      125. 内心三角形の反中点三角形のジェルゴンヌ三角形
      126. 内心三角形の反中点三角形のナーゲル三角形
      127. 内心三角形の内心三角形の中点三角形
      128. 内心三角形の内心三角形の反中点三角形
      129. 内心三角形の内心三角形の内心三角形
      130. 内心三角形の内心三角形の傍心三角形
      131. 内心三角形の内心三角形のジェルゴンヌ三角形
      132. 内心三角形の内心三角形のナーゲル三角形
      133. 内心三角形の傍心三角形の中点三角形
      134. 内心三角形の傍心三角形の反中点三角形
      135. 内心三角形の傍心三角形の内心三角形
      136. 内心三角形の傍心三角形の傍心三角形
      137. 内心三角形の傍心三角形のジェルゴンヌ三角形
      138. 内心三角形の傍心三角形のナーゲル三角形
      139. 内心三角形のジェルゴンヌ三角形の中点三角形
      140. 内心三角形のジェルゴンヌ三角形の反中点三角形
      141. 内心三角形のジェルゴンヌ三角形の内心三角形
      142. 内心三角形のジェルゴンヌ三角形の傍心三角形
      143. 内心三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      144. 内心三角形のジェルゴンヌ三角形のナーゲル三角形
      145. 内心三角形のナーゲル三角形の中点三角形
      146. 内心三角形のナーゲル三角形の反中点三角形
      147. 内心三角形のナーゲル三角形の内心三角形
      148. 内心三角形のナーゲル三角形の傍心三角形
      149. 内心三角形のナーゲル三角形のジェルゴンヌ三角形
      150. 内心三角形のナーゲル三角形のナーゲル三角形
      151. 傍心三角形の中点三角形の中点三角形
      152. 傍心三角形の中点三角形の反中点三角形
      153. 傍心三角形の中点三角形の内心三角形
      154. 傍心三角形の中点三角形の傍心三角形
      155. 傍心三角形の中点三角形のジェルゴンヌ三角形
      156. 傍心三角形の中点三角形のナーゲル三角形
      157. 傍心三角形の反中点三角形の中点三角形
      158. 傍心三角形の反中点三角形の反中点三角形
      159. 傍心三角形の反中点三角形の内心三角形
      160. 傍心三角形の反中点三角形の傍心三角形
      161. 傍心三角形の反中点三角形のジェルゴンヌ三角形
      162. 傍心三角形の反中点三角形のナーゲル三角形
      163. 傍心三角形の内心三角形の中点三角形
      164. 傍心三角形の内心三角形の反中点三角形
      165. 傍心三角形の内心三角形の内心三角形
      166. 傍心三角形の内心三角形の傍心三角形
      167. 傍心三角形の内心三角形のジェルゴンヌ三角形
      168. 傍心三角形の内心三角形のナーゲル三角形
      169. 傍心三角形の傍心三角形の中点三角形
      170. 傍心三角形の傍心三角形の反中点三角形
      171. 傍心三角形の傍心三角形の内心三角形
      172. 傍心三角形の傍心三角形の傍心三角形
      173. 傍心三角形の傍心三角形のジェルゴンヌ三角形
      174. 傍心三角形の傍心三角形のナーゲル三角形
      175. 傍心三角形のジェルゴンヌ三角形の中点三角形
      176. 傍心三角形のジェルゴンヌ三角形の反中点三角形
      177. 傍心三角形のジェルゴンヌ三角形の内心三角形
      178. 傍心三角形のジェルゴンヌ三角形の傍心三角形
      179. 傍心三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      180. 傍心三角形のジェルゴンヌ三角形のナーゲル三角形
      181. 傍心三角形のナーゲル三角形の中点三角形
      182. 傍心三角形のナーゲル三角形の反中点三角形
      183. 傍心三角形のナーゲル三角形の内心三角形
      184. 傍心三角形のナーゲル三角形の傍心三角形
      185. 傍心三角形のナーゲル三角形のジェルゴンヌ三角形
      186. 傍心三角形のナーゲル三角形のナーゲル三角形
      187. ジェルゴンヌ三角形の中点三角形の中点三角形
      188. ジェルゴンヌ三角形の中点三角形の反中点三角形
      189. ジェルゴンヌ三角形の中点三角形の内心三角形
      190. ジェルゴンヌ三角形の中点三角形の傍心三角形
      191. ジェルゴンヌ三角形の中点三角形のジェルゴンヌ三角形
      192. ジェルゴンヌ三角形の中点三角形のナーゲル三角形
      193. ジェルゴンヌ三角形の反中点三角形の中点三角形
      194. ジェルゴンヌ三角形の反中点三角形の反中点三角形
      195. ジェルゴンヌ三角形の反中点三角形の内心三角形
      196. ジェルゴンヌ三角形の反中点三角形の傍心三角形
      197. ジェルゴンヌ三角形の反中点三角形のジェルゴンヌ三角形
      198. ジェルゴンヌ三角形の反中点三角形のナーゲル三角形
      199. ジェルゴンヌ三角形の内心三角形の中点三角形
      200. ジェルゴンヌ三角形の内心三角形の反中点三角形
      201. ジェルゴンヌ三角形の内心三角形の内心三角形
      202. ジェルゴンヌ三角形の内心三角形の傍心三角形
      203. ジェルゴンヌ三角形の内心三角形のジェルゴンヌ三角形
      204. ジェルゴンヌ三角形の内心三角形のナーゲル三角形
      205. ジェルゴンヌ三角形の傍心三角形の中点三角形
      206. ジェルゴンヌ三角形の傍心三角形の反中点三角形
      207. ジェルゴンヌ三角形の傍心三角形の内心三角形
      208. ジェルゴンヌ三角形の傍心三角形の傍心三角形
      209. ジェルゴンヌ三角形の傍心三角形のジェルゴンヌ三角形
      210. ジェルゴンヌ三角形の傍心三角形のナーゲル三角形
      211. ジェルゴンヌ三角形のジェルゴンヌ三角形の中点三角形
      212. ジェルゴンヌ三角形のジェルゴンヌ三角形の反中点三角形
      213. ジェルゴンヌ三角形のジェルゴンヌ三角形の内心三角形
      214. ジェルゴンヌ三角形のジェルゴンヌ三角形の傍心三角形
      215. ジェルゴンヌ三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      216. ジェルゴンヌ三角形のジェルゴンヌ三角形のナーゲル三角形
      217. ジェルゴンヌ三角形のナーゲル三角形の中点三角形
      218. ジェルゴンヌ三角形のナーゲル三角形の反中点三角形
      219. ジェルゴンヌ三角形のナーゲル三角形の内心三角形
      220. ジェルゴンヌ三角形のナーゲル三角形の傍心三角形
      221. ジェルゴンヌ三角形のナーゲル三角形のジェルゴンヌ三角形
      222. ジェルゴンヌ三角形のナーゲル三角形のナーゲル三角形
      223. ナーゲル三角形の中点三角形の中点三角形
      224. ナーゲル三角形の中点三角形の反中点三角形
      225. ナーゲル三角形の中点三角形の内心三角形
      226. ナーゲル三角形の中点三角形の傍心三角形
      227. ナーゲル三角形の中点三角形のジェルゴンヌ三角形
      228. ナーゲル三角形の中点三角形のナーゲル三角形
      229. ナーゲル三角形の反中点三角形の中点三角形
      230. ナーゲル三角形の反中点三角形の反中点三角形
      231. ナーゲル三角形の反中点三角形の内心三角形
      232. ナーゲル三角形の反中点三角形の傍心三角形
      233. ナーゲル三角形の反中点三角形のジェルゴンヌ三角形
      234. ナーゲル三角形の反中点三角形のナーゲル三角形
      235. ナーゲル三角形の内心三角形の中点三角形
      236. ナーゲル三角形の内心三角形の反中点三角形
      237. ナーゲル三角形の内心三角形の内心三角形
      238. ナーゲル三角形の内心三角形の傍心三角形
      239. ナーゲル三角形の内心三角形のジェルゴンヌ三角形
      240. ナーゲル三角形の内心三角形のナーゲル三角形
      241. ナーゲル三角形の傍心三角形の中点三角形
      242. ナーゲル三角形の傍心三角形の反中点三角形
      243. ナーゲル三角形の傍心三角形の内心三角形
      244. ナーゲル三角形の傍心三角形の傍心三角形
      245. ナーゲル三角形の傍心三角形のジェルゴンヌ三角形
      246. ナーゲル三角形の傍心三角形のナーゲル三角形
      247. ナーゲル三角形のジェルゴンヌ三角形の中点三角形
      248. ナーゲル三角形のジェルゴンヌ三角形の反中点三角形
      249. ナーゲル三角形のジェルゴンヌ三角形の内心三角形
      250. ナーゲル三角形のジェルゴンヌ三角形の傍心三角形
      251. ナーゲル三角形のジェルゴンヌ三角形のジェルゴンヌ三角形
      252. ナーゲル三角形のジェルゴンヌ三角形のナーゲル三角形
      253. ナーゲル三角形のナーゲル三角形の中点三角形
      254. ナーゲル三角形のナーゲル三角形の反中点三角形
      255. ナーゲル三角形のナーゲル三角形の内心三角形
      256. ナーゲル三角形のナーゲル三角形の傍心三角形
      257. ナーゲル三角形のナーゲル三角形のジェルゴンヌ三角形
      258. ナーゲル三角形のナーゲル三角形のナーゲル三角形

      つまり、疑似コードで書くとこんな順番です。

      for X in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
        Xを計算して表示する;
      od
      for X in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
        for Y in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
          XのYを計算して表示する;
        od
      od
      for X in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
        for Y in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
          for Z in [中点三角形, 反中点三角形, 内心三角形, 傍心三角形, ジェルゴンヌ三角形, ナーゲル三角形] do
            XのYのZを計算して表示する;
          od
        od
      od
      

   関数を設計するヒント

   元の三角形の頂点の座標から中点三角形の頂点の座標を計算する関数のプロトタイプ宣言の例

   方法1

   void medial_triangle(double xA, double yA, double xB, double yB, double xC, double yC, double *xAp, double *yAp, double *xBp, double *yBp, double *xCp, double *yCp);

   方法2

   void medial_triangle(const double reference[6], double central[6]);

   方法3

   void medial_triangle(const double reference[3][2], double central[3][2]);

   方法4

   struct point {
           double  x, y;
   };
   struct triangle {
           struct point    A, B, C;
   };
   struct triangle medial_triangle(struct triangle reference);

   方法5

   struct point {
           double  x, y;
   };
   struct triangle {
           struct point    A, B, C;
   };
   void medial_triangle(const struct triangle *reference, struct triangle *central);

   方法6

   struct point {
           double  coordinates[2];
   };
   struct triangle {
           struct point    vertices[3];
   };
   struct triangle medial_triangle(struct triangle reference);

   方法7

   struct point {
           double  coordinates[2];
   };
   struct triangle {
           struct point    vertices[3];
   };
   void medial_triangle(const struct triangle *reference, struct triangle *central);

   …

   …