QOJ.ac

QOJ

時間限制: 3 s 記憶體限制: 2048 MB 總分: 100

#8682. 水の世界

统计

近年、太陽系の外で何千もの惑星が発見されています。生命を支えられる可能性を左右する重要な要因の一つが、液体の水の存在です。遠い惑星で水を検出するのは簡単ではありません。自転する惑星については、相対論的量子偏光分光法を用いたまったく新しい技術が役立ちます。その仕組みは次のとおりです(本当の仕組みを理解している人は地球上に 3 人しかいないため、これは簡略化した説明です)。

望遠鏡に映る惑星は、自転軸が垂直、赤道が水平になっているとします。惑星表面の解像度が最も高くなるため、画像の中央の垂直線(自転軸と重なる線)だけを解析します。

解析は $d$ 度ずつのステップで進みます。1 ステップでは、惑星が $d$ 度自転する間のデータを集約するので、各ステップで惑星表面の $d$ 度分の切片の情報が得られます。画像を高さの等しい $n$ 個の区間に分け、それぞれを解析します。つまり $d$ 度分の切片を $n$ 個の領域 $A_1,\ldots,A_n$ に分割します。各領域 $A_i$ について、画像解析により $A_i$ が水で覆われている割合を百分率で表す数値が得られます。右の図には、1 ステップ分の領域 $A_i$ が強調表示されています。

problem_8682_2139e876b51353495856aca74a78657b.png

惑星の表面は球面と仮定してかまいません。したがって各領域 $A_2,\ldots,A_{n-1}$ は球面四辺形です。頂点が四つあり、二辺は赤道に平行(すなわち赤道面と平行な平面上)で、残る二辺は惑星の両極を通る大円上にあり、その大円間の角度は $d$ 度です。どちらの極でも四頂点のうち二つが極で重なるので、$A_1$ と $A_n$ は赤道に平行な辺を一つだけ持つ球面三角形です。表面の曲率により、赤道に平行な辺は赤道に近いほど長くなり、大円上の辺は極に近いほど長くなります。

次の $d$ 度の自転について同じ過程を繰り返し、惑星表面全体を覆うまで合計 $m$ 回行います(つまり $md=360$ 度です)。与えられたデータから、惑星表面が水で覆われている割合を百分率で計算してください。

入力

入力の最初の行には二つの整数 $n$ と $m$($2 \le n,m \le 1000$)があります。続く $n$ 行はそれぞれ $m$ 個の整数 $a_{i,j}$($1 \le i \le n$、$1 \le j \le m$ に対して $0 \le a_{i,j} \le 100$)を含みます。この行列の各列は、1 ステップ、すなわち $d$ 度の自転に対する測定値を表します。$a_{i,j}$ は、第 $j$ ステップで領域 $A_i$ が水で覆われている割合の百分率です。

出力

惑星表面が水で覆われている割合を百分率で出力してください。解答の絶対誤差は $10^{-6}$ 以下でなければなりません。

入出力例

入力 1

3 7
63 61 55 54 77 87 89
73 60 38 5 16 56 91
75 43 11 3 16 20 95

出力 1

51.809523810

入力 2

4 3
10 10 10
10 10 10
10 10 10
10 10 10

出力 2

10.000000000

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.