← 返回题目列表

AtCoder · joisc2021_a6

A6. 特技飞行

中文机器翻译题面 查看原题

以下是来自日本的原始新闻PDF,已完整保存并染色。

曲芸飛行 (Aerobatics) - 原题 PDF 第 1 页
原题PDF第1页
曲芸飛行 (Aerobatics) - 原题 PDF 第 2 页
原题PDF第2页
曲芸飛行 (Aerobatics) - 原题 PDF 第 3 页
原题PDF第3页
曲芸飛行 (Aerobatics) - 原题 PDF 第 4 页
原题PDF第4页
可复制的 PDF 提取文本
The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 1 – Aerobatics

                   曲芸飛行(Aerobatics)
                    出力のみの課題(Output Only Task)





 ビ太郎は曲芸飛行の競技に出場する予定である.この競技は,チェックポイントを通りながら飛行機を一

定の高さで飛行させるものである.ここで,飛行機が飛ぶ領域は座標平面で表される.チェックポイントは

N 個あり,1 からN までの番号が付けられている.チェックポイントi (1 ≦i ≦N) の座標は(Xi, Yi) である.
 競技中,ビ太郎は飛行機でN 個のチェックポイントを一度ずつ通らなければならない.具体的には,以

下の行動を順に行う必要がある.

    1. まず,N 個のチェックポイントのうち1 つをスタート地点として選び,ここから飛行を開始する.

    2. 次の行動をN −1 回繰り返す.

     まだ到達したことがないチェックポイントを1 つ選び,現在いる地点から選んだチェックポイン

     トに向けて直進する.

    3. 最後にたどり着いたチェックポイントで,飛行を終了する.

 ただし2. では,スタート地点は既に到達したチェックポイントとしてみなすものとする.また,ある

チェックポイントから次のチェックポイントに向けて飛行するときに,曲線を描いたり途中で曲がったりし

てはならず,直進しなければならない.

 すると,飛行機のルートは折れ線で表され,競技中に飛行機の方向を変えるタイミングが最大N −2 回あ

ることになる.チェックポイントにおける折れ線の角度が小さいと,高速に動く飛行機を方向転換させる角

度が大きくなり,操縦に失敗するリスクが高まってしまう.

 そこで,ビ太郎は,飛行機の操縦に成功する確率を上げるために,飛行開始地点と飛行終了地点を除く

N −2 個のチェックポイントにおける折れ線の角度の最小値をできるだけ大きくしたい.

 チェックポイントの座標が与えられたとき,折れ線の角度の最小値ができるだけ大きくなるようにチェッ

クポイントを通る順番を決めよ.


入力

 入力は以下の形式で与えられる.入力される値はすべて整数である.ただし,Z0 は採点のために使われ

る整数である.

    N Z0
      X1 Y1
                                 ...

     XN YN



                       曲芸飛行– 1 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 1 – Aerobatics



出力

 N 行で出力せよ.k 行目(1 ≦k ≦N) には,k 番目に到達するチェックポイントの番号Pk (1 ≦Pk ≦N) を
出力せよ.ただし,スタート地点は1 番目に到達するチェックポイントP1 とする.


提出方法

 入力データinput 01.txt, input 02.txt,  ..., input 06.txt に対する出力データoutput 01.txt,

output 02.txt, ..., output 06.txt のみを提出せよ.


制約

    • 3 ≦N ≦1 000.
    √
    •   Xi2 + Yi2 ≦10 000 000 (1 ≦i ≦N).
    • (Xi, Yi) , (Xj, Yj) (1 ≦i <  j ≦N).
    • 1 ≦Z0 ≦179.


配布ライブラリ

 この課題では,3 個の点がなす角を計算する関数をライブラリとして利用できる.これはアーカイブの中

に含まれるファイルaerobatics.h に含まれており,次のような仕様となっている.

    • double GetAngle(int xa, int ya, int xb, int yb, int xc, int yc)

   この関数は,以下のように点A, B,C を定めたときに,角BAC の大きさ(度) を0 以上180 以下の実

   数値で,十分小さい誤差で返すものとなっている.引数の順序を間違えないように注意すること.

    ◦点A について,引数xa は点A のx 座標,引数ya は点A のy 座標を表す.

    ◦点B について,引数xb は点B のx 座標,引数yb は点B のy 座標を表す.

    ◦点C について,引数xc は点C のx 座標,引数yc は点C のy 座標を表す.

    ◦ただし,点A と点B が同じ位置,または点A と点C が同じ位置にあるように引数が指定された

     場合の挙動は定義されない.

 この課題の解答を求めるプログラムには,配布ライブラリの関数GetAngle を使用しても,使用しなくて

もよい.また,使用する場合は,関数GetAngle の中身を改変して使用しても構わない.

 なお,関数GetAngle は,この課題の採点プログラムで用いられるものと同一である.





                       曲芸飛行– 2 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 1 – Aerobatics



採点基準


 各入力データに対し,得点は以下のように計算される.

 あなたの出力が誤っている場合,すなわち出力されたP1, P2, . . . , PN が1, 2, . . . , N の並び替えではない場
合や,出力が指定された形式に沿っていない場合は,あなたの得点は0 点となる.

 あなたの出力が正しい場合,あなたの指定した飛行機のルートを折れ線で表したときの,飛行開始地点と

飛行終了地点を除くN −2 個のチェックポイントにおける折れ線の角度の最小値をZ (度) とし,その入力

データに対する配点をS とすると,あなたの得点は以下のように計算される.

    • Z ≧Z0 の場合,S 点.
                          f(Z/180)
    • Z < Z0 の場合,S ×     点.
                          f(Z0/180)

 ただし,関数f(α) (0 ≦α ≦1) は次のように定義される.

                                              f(α) = 4α4 + α

  6 個の入力データの得点の合計を,小数点以下を四捨五入することで整数に丸めたものが,この課題の得

点である.

 各入力データにおける,N, Z0 の値と配点は,以下の通りである.


              小課題   入力データ    N    Z0 配点
                              1  input 01.txt    15  100    10

                              2  input 02.txt   200  143    15

                              3  input 03.txt   200  134    15

                              4  input 04.txt  1000  156    20

                              5  input 05.txt  1000  150    20

                              6  input 06.txt  1000  153    20





                       曲芸飛行– 3 / 4

The 20th Japanese Olympiad in Informatics (JOI 2020/2021)

                                                         Spring Training Camp/Qualifying Trial

                                                  March 20–23, 2021 (Komaba, Tokyo)


                                                                      Contest Day 1 – Aerobatics



入出力例

  入力例1              出力例1

   7 90                           5

   3 1                            3

   2 5                            1

   0 2                            7

   -1 6                           6

   -3 1                           4

   -1 -4                          2

   4 -2

 チェックポイント5, 3, 1, 7, 6, 4, 2 の順に進む場合,ビ太郎の飛行機のルートは下図のようになる.このと
き,最も角が小さくなるのはチェックポイント6 で,この角度は68.19859 · · · 度である.Z0 = 90 (度) なの
で,この通りに出力すると配点の約61.5 % の点数が得られる.



                                                 y


                                       4

                                                      2





                                            3

                              5                           1

                                                                                       x




                                                               7




                                       6





                       曲芸飛行– 4 / 4