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

練習問題

2017年10月12日出題
  1. 標準入力から整数を次々に入力し、以下の通り、標準出力に出力するプログラムを書け。入力値はlong longにおさまると仮定してかまわない。入力の個数は事前にはわからないものとする。

    1. 入力値ごとに、それまでの入力の最小値、その値、それまでの入力の最大値を出力せよ。すなわち、入力が \[ \begin{matrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \end{matrix} \] ならば、出力は \[ \begin{matrix} x_0 & x_0 & x_0 \\ \min\{x_0,x_1\} & x_1 & \max\{x_0,x_1\} \\ \min\{x_0,x_1,x_2\} & x_2 & \max\{x_0,x_1,x_2\} \\ \min\{x_0,x_1,x_2,x_3\} & x_3 & \max\{x_0,x_1,x_2,x_3\} \\ \vdots & \vdots & \vdots \\ \min\{x_0,x_1,x_2,\ldots,x_{n-1}\} & x_{n-1} & \max\{x_0,x_1,x_2,\ldots,x_{n-1}\} \end{matrix} \] となるようにせよ。

    2. 最初の2個を除く入力値ごとに、それまで3個の入力の最小値と最大値を出力せよ。すなわち、入力が \[ \begin{matrix} x_0 \\ x_1 \\ x_2 \\ x_3 \\ \vdots \\ x_{n-1} \end{matrix} \] ならば、出力は \[ \begin{matrix} \min\{x_0,x_1,x_2\} & \max\{x_0,x_1,x_2\} \\ \min\{x_1,x_2,x_3\} & \max\{x_1,x_2,x_3\} \\ \vdots & \vdots \\ \min\{x_{n-3},x_{n-2},x_{n-1}\} & \max\{x_{n-3},x_{n-2},x_{n-1}\} \end{matrix} \] となるようにせよ。

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

    成分で書き下すと、 \[ A=(x_A,y_A),\qquad B=(x_B,y_B),\qquad C=(x_C,y_C),\qquad X=\lambda:\mu:\nu \] のとき \[ X= \left( \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} \right) \] である。

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

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

    中点三角形
    元の三角形の辺の中点を結ぶ三角形 \[ \begin{aligned} A' &= 0:1:1 \\ B' &= 1:0:1 \\ C' &= 1:1:0 \end{aligned} \]
    中点三角形
    反中点三角形
    元の三角形の頂点を通り対辺に平行な直線から構成される三角形 \[ \begin{aligned} A' &= -1:1:1 \\ B' &= 1:-1:1 \\ C' &= 1:1:-1 \end{aligned} \]
    反中点三角形
    内心三角形
    元の三角形の角の二等分線と対辺の交点を結ぶ三角形 \[ \begin{aligned} A' &= 0:b:c \\ B' &= a:0:c \\ C' &= a:b:0 \end{aligned} \]
    内心三角形
    傍心三角形
    元の三角形の傍心を結ぶ三角形 \[ \begin{aligned} A' &= -a:b:c \\ B' &= a:-b:c \\ C' &= a:b:-c \end{aligned} \]
    傍心三角形
    ジェルゴンヌ三角形
    元の三角形の内接円と辺の接点を結ぶ三角形 \[ \begin{aligned} A' &= 0:(a+b-c):(a-b+c) \\ B' &= (a+b-c):0:(-a+b+c) \\ C' &= (a-b+c):(-a+b+c):0 \end{aligned} \]
    ジェルゴンヌ三角形
    ナーゲル三角形
    元の三角形の傍接円と対応する辺の接点を結ぶ三角形 \[ \begin{aligned} A' &= 0:(a-b+c):(a+b-c) \\ B' &= (-a+b+c):0:(a+b-c) \\ C' &= (-a+b+c):(a-b+c):0 \end{aligned} \]
    ナーゲル三角形
    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. ナーゲル三角形のナーゲル三角形

参考データ

\(A=(0,0)\), \(B=(1+\sqrt{3},0)\), \(C=(1,1)\) の場合
\(A'\) \(B'\) \(C'\)
\(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標
元の三角形 0.000000000000 0.000000000000 2.732050807569 0.000000000000 1.000000000000 1.000000000000
i. 中点三角形 1.866025403784 0.500000000000 0.500000000000 0.500000000000 1.366025403784 0.000000000000
ii. 反中点三角形 3.732050807569 1.000000000000 -1.732050807569 1.000000000000 1.732050807569 -1.000000000000
iii. 内心三角形 1.590770275176 0.658918622598 0.577350269190 0.577350269190 1.131652497587 0.000000000000
iv. 傍心三角形 3.073132184971 1.272933029980 -0.341081377402 0.823443287197 1.658918622598 -4.004983837549
v. ジェルゴンヌ三角形 1.295385137588 0.829459311299 0.758819045103 0.758819045103 1.073132184971 0.000000000000
vi. ナーゲル三角形 2.436665669981 0.170540688701 0.241180954897 0.241180954897 1.658918622598 0.000000000000
vii. 中点三角形の中点三角形 0.933012701892 0.250000000000 1.616025403784 0.250000000000 1.183012701892 0.500000000000
viii. 中点三角形の反中点三角形 0.000000000000 0.000000000000 2.732050807569 0.000000000000 1.000000000000 1.000000000000
ix. 中点三角形の内心三角形 1.070640266196 0.170540688701 1.577350269190 0.211324865405 1.300199154991 0.500000000000
x. 中点三角形の傍心三角形 0.329459311299 -0.136466514990 2.036566092485 0.088278356401 1.036566092485 2.502491918775
xi. 中点三角形のジェルゴンヌ三角形 1.218332834990 0.085270344351 1.486615881233 0.120590477449 1.329459311299 0.500000000000
xii. 中点三角形のナーゲル三角形 0.647692568794 0.414729655649 1.745434926336 0.379409522551 1.036566092485 0.500000000000
xiii. 反中点三角形の中点三角形 0.000000000000 0.000000000000 2.732050807569 0.000000000000 1.000000000000 1.000000000000
xiv. 反中点三角形の反中点三角形 -3.732050807569 -1.000000000000 7.196152422707 -1.000000000000 0.267949192431 3.000000000000
xv. 反中点三角形の内心三角形 0.550510257217 -0.317837245196 2.577350269190 -0.154700538379 1.468745812394 1.000000000000
xvi. 反中点三角形の傍心三角形 -2.414213562373 -1.545866059960 4.414213562373 -0.646886574394 0.414213562373 9.009967675098
xvii. 反中点三角形のジェルゴンヌ三角形 1.141280532393 -0.658918622598 2.214412717364 -0.517638090205 1.585786437627 1.000000000000
xviii. 反中点三角形のナーゲル三角形 -1.141280532393 0.658918622598 3.249688897774 0.517638090205 0.414213562373 1.000000000000
xix. 内心三角形の中点三角形 0.854501383389 0.288675134595 1.361211386382 0.329459311299 1.084060272183 0.618134445894
xx. 内心三角形の反中点三角形 0.118232491601 -0.081568353408 2.145072503574 0.081568353408 1.036468046778 1.236268891788
xxi. 内心三角形の内心三角形 0.887032500423 0.254791364668 1.333881015222 0.290235191914 1.083197339101 0.618064989962
xxii. 内心三角形の傍心三角形 0.334519601929 -0.062493752956 1.933078909187 0.062830356710 0.999238084432 1.688998973381
xxiii. 内心三角形のジェルゴンヌ三角形 0.928467507595 0.211633478376 1.299374441866 0.240711899861 1.082699317062 0.618024905064
xxiv. 内心三角形のナーゲル三角形 0.780535259182 0.365716790814 1.423048330898 0.418206722737 1.085421227304 0.618243986723
xxv. 傍心三角形の中点三角形 0.658918622598 -1.590770275176 2.366025403784 -1.366025403784 1.366025403784 1.048188158589
xxvi. 傍心三角形の反中点三角形 -1.755294939775 -4.454473580332 5.073132184971 -3.555494094766 1.073132184971 6.101360154726
xxvii. 傍心三角形の内心三角形 0.432102538275 -1.043187808239 2.511409843752 -0.823443287197 1.328043972047 1.043187808239
xxviii. 傍心三角形の傍心三角形 -3.317074292159 -4.331127644126 7.373279182485 -3.630444858679 1.170809922217 3.442115833658
xxix. 傍心三角形のジェルゴンヌ三角形 0.272326664760 -0.657454727458 2.596707865933 -0.505106734631 1.248117944784 1.032665347127
xxx. 傍心三角形のナーゲル三角形 1.045510580436 -2.524085822894 2.135342941636 -2.226944072938 1.483932862785 1.063710970050
xxxi. ジェルゴンヌ三角形の中点三角形 0.915975615037 0.379409522551 1.184258661280 0.414729655649 1.027102091345 0.794139178201
xxxii. ジェルゴンヌ三角形の反中点三角形 0.536566092485 -0.070640266196 1.609698277456 0.070640266196 0.981071997720 1.588278356401
xxxiii. ジェルゴンヌ三角形の内心三角形 0.880329977219 0.465465704811 1.207106781187 0.500000000000 1.021133059812 0.793353340291
xxxiv. ジェルゴンヌ三角形の傍心三角形 0.291122206471 -0.051255641947 1.971181489930 0.058861261226 0.996422695864 1.170360640285
xxxv. ジェルゴンヌ三角形のジェルゴンヌ三角形 0.855220148979 0.526086192697 1.220511925775 0.550028680686 1.008572159519 0.791699666396
xxxvi. ジェルゴンヌ三角形のナーゲル三角形 0.976731081095 0.232732852406 1.148005396784 0.279430630613 1.045632023171 0.796578690006
xxxvii. ナーゲル三角形の中点三角形 0.950049788748 0.120590477449 2.047792146289 0.085270344351 1.338923312439 0.205860821799
xxxviii. ナーゲル三角形の反中点三角形 -0.536566092485 0.070640266196 3.854403337681 -0.070640266196 1.018928002280 0.411721643599
xxxix. ナーゲル三角形の内心三角形 1.281739691603 0.064164462028 1.966639850339 0.067475653278 1.654283710757 0.195714022629
xl. ナーゲル三角形の傍心三角形 0.213454640634 -0.034231569286 2.450646606751 0.018749752110 1.384299751249 11.596070398786
xli. ナーゲル三角形のジェルゴンヌ三角形 1.640330580080 0.003162137782 1.677336139020 0.004038505765 1.659697616261 0.195539828874
xlii. ナーゲル三角形のナーゲル三角形 0.259768997415 0.238018817115 2.418248153558 0.166502182936 1.018149008618 0.216181814724
\(A=(1,0)\), \(B=(-1/2,\sqrt{3}/2)\), \(C=(0,-1)\) の場合
\(A'\) \(B'\) \(C'\)
\(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標 \(x\)座標 \(y\)座標
元の三角形 1.000000000000 0.000000000000 -0.500000000000 0.866025403784 0.000000000000 -1.000000000000
i. 中点三角形 -0.250000000000 -0.066987298108 0.500000000000 -0.500000000000 0.250000000000 0.433012701892
ii. 反中点三角形 -1.500000000000 -0.133974596216 1.500000000000 -1.866025403784 0.500000000000 1.866025403784
iii. 内心三角形 -0.224744871392 -0.161240721226 0.527266125010 -0.472733874990 0.366025403784 0.366025403784
iv. 傍心三角形 -2.173032607476 -0.417737667700 1.173032607476 -1.314313139868 0.758819045103 1.831951230074
v. ジェルゴンヌ三角形 -0.208868833850 -0.220490899953 0.570640266196 -0.429359733804 0.474143868042 0.303603179341
vi. ナーゲル三角形 -0.291131166150 0.086516303738 0.429359733804 -0.570640266196 0.025856131958 0.562422224443
vii. 中点三角形の中点三角形 0.375000000000 -0.033493649054 0.000000000000 0.183012701892 0.125000000000 -0.283493649054
viii. 中点三角形の反中点三角形 1.000000000000 0.000000000000 -0.500000000000 0.866025403784 0.000000000000 -1.000000000000
ix. 中点三角形の内心三角形 0.362372435696 0.013633062505 -0.013633062505 0.169379639387 0.066987298108 -0.250000000000
x. 中点三角形の傍心三角形 1.336516303738 0.141881535742 -0.336516303738 0.590169271826 -0.129409522551 -0.982962913145
xi. 中点三角形のジェルゴンヌ三角形 0.354434416925 0.043258151869 -0.035320133098 0.147692568794 0.012928065979 -0.218788887778
xii. 中点三角形のナーゲル三角形 0.395565583075 -0.110245449977 0.035320133098 0.218332834990 0.237071934021 -0.348198410330
xiii. 反中点三角形の中点三角形 1.000000000000 0.000000000000 -0.500000000000 0.866025403784 0.000000000000 -1.000000000000
xiv. 反中点三角形の反中点三角形 3.500000000000 0.133974596216 -2.500000000000 3.598076211353 -0.500000000000 -3.866025403784
xv. 反中点三角形の内心三角形 0.949489742783 0.188506846237 -0.554532250021 0.811493153763 -0.232050807569 -0.866025403784
xvi. 反中点三角形の傍心三角形 4.846065214951 0.701500739185 -1.846065214951 2.494651683521 -1.017638090205 -3.797877056363
xvii. 反中点三角形のジェルゴンヌ三角形 0.917737667700 0.307007203691 -0.641280532393 0.724744871392 -0.448287736084 -0.741180954897
xviii. 反中点三角形のナーゲル三角形 1.082262332300 -0.307007203691 -0.358719467607 1.007305936177 0.448287736084 -1.258819045103
xix. 内心三角形の中点三角形 0.446645764397 -0.053354235603 0.070640266196 0.102392341279 0.151260626809 -0.316987298108
xx. 内心三角形の反中点三角形 1.118036400187 0.054532250021 -0.385985592618 0.677518557548 -0.063504150166 -1.000000000000
xxi. 内心三角形の内心三角形 0.445534950220 -0.047575883266 0.063531195563 0.096047451763 0.137035244219 -0.311094951709
xxii. 内心三角形の傍心三角形 1.207139140294 0.081575575666 -0.355538188587 0.610045482066 -0.086995079572 -0.973549149632
xxiii. 内心三角形のジェルゴンヌ三角形 0.444557334369 -0.042490416270 0.055664421007 0.089026306809 0.122494924079 -0.305072153906
xxiv. 内心三角形のナーゲル三角形 0.448734194426 -0.064218054935 0.085616111386 0.115758375749 0.180026329540 -0.328902442310
xxv. 傍心三角形の中点三角形 0.965925826289 0.258819045103 -0.707106781187 0.707106781187 -0.500000000000 -0.866025403784
xxvi. 傍心三角形の反中点三角形 4.104884260054 0.935375757905 -2.587246169849 2.728526702242 -1.758819045103 -3.564002037642
xxvii. 傍心三角形の内心三角形 0.972620026711 0.207971544720 -0.642906938261 0.756369053288 -0.372833452485 -0.900099577495
xxviii. 傍心三角形の傍心三角形 3.476869716073 0.706097778940 -2.923955445457 3.357406371225 -1.524185909833 -3.679710295096
xxix. 傍心三角形のジェルゴンヌ三角形 0.981028784543 0.144100687832 -0.591797532550 0.795586679629 -0.247842759855 -0.933590732647
xxx. 傍心三角形のナーゲル三角形 0.950822868035 0.373537402374 -0.822416029823 0.618626882744 -0.752157240145 -0.798460074922
xxxi. ジェルゴンヌ三角形の中点三角形 0.522392067119 -0.062878277231 0.132637517096 0.041556139694 0.180885716173 -0.324925316878
xxxii. ジェルゴンヌ三角形の反中点三角形 1.253652968089 0.094734345491 -0.305365232005 0.512472013191 -0.112372435696 -0.953453813098
xxxiii. ジェルゴンヌ三角形の内心三角形 0.523951567551 -0.074723859047 0.147593699527 0.053032422111 0.210510805537 -0.332863335649
xxxiv. ジェルゴンヌ三角形の傍心三角形 1.107348870426 0.041321079591 -0.383806005733 0.658977652895 -0.057711616983 -0.980409545829
xxxv. ジェルゴンヌ三角形のジェルゴンヌ三角形 0.525910496271 -0.089603399932 0.159500295571 0.062168674590 0.239629001408 -0.340665532718
xxxvi. ジェルゴンヌ三角形のナーゲル三角形 0.518873637967 -0.036153154530 0.105774738621 0.020943604798 0.122142430938 -0.309185101039
xxxvii. ナーゲル三角形の中点三角形 0.227607932881 -0.004109020876 -0.132637517096 0.324469264091 0.069114283827 -0.242061981229
xxxviii. ナーゲル三角形の反中点三角形 0.746347031911 -0.094734345491 -0.694634767995 1.219578794378 0.112372435696 -1.046546186902
xxxix. ナーゲル三角形の内心三角形 0.175002949376 0.143608950804 -0.149199997386 0.299603338931 -0.058971915120 -0.125235124483
xl. ナーゲル三角形の傍心三角形 1.803770271748 0.343102261404 -0.355177728422 0.609425805947 -0.162451538990 -0.964091213592
xli. ナーゲル三角形のジェルゴンヌ三角形 0.159948019723 0.185884102774 -0.195721454322 0.229758783871 -0.163971350834 -0.029465602587
xlii. ナーゲル三角形のナーゲル三角形 0.295267846038 -0.194102144527 -0.069553579870 0.419179744310 0.302199918488 -0.454658359871

戻る