No.3100 Parallel Translated
タグ : / 解いたユーザー数 54
作問者 :
shobonvip
/ テスター :
noya2
問題文
$2$ 次元ユークリッド空間上の $N$ 頂点凸多角形 $P$ が与えられます。 $P$ の頂点は頂点 $1, 2, \cdots, N$ と番号付けられています。頂点 $i$ $(1\le i \le N)$ は座標 $(X_i, Y_i)$ にあり、 $P$ の辺は頂点 $i$ と頂点 $i+1$ を結ぶ $N$ 個の辺からなります。ただし、頂点 $N+1$ は頂点 $1$ を指すものとします。
$0$ 以上 $1$ 未満の実数を一様ランダムに $2$ つとり、 $p, q$ とします。 $P$ に含まれる点をすべて $(p, q)$ だけ平行移動した多角形
$$Q = \{(x+p, y+q) \mid (x, y) \in P\}$$
の内部に含まれる格子点の個数の期待値を $\mathrm{mod} ~ {998244353}$ で求めてください。
注記
求める期待値は必ず有理数になることが証明できます。また、この問題の制約下では、その値を互いに素な正整数 $P, Q$ により既約分数 $\frac{P}{Q}$ で表したとき、 $Q \not \equiv 0 \pmod{998244353}$ となることも証明できます。このとき、 $R \times Q \equiv P \pmod{998244353}$ かつ $0 \le R < 998244353$ を満たす整数 $R$ が一意に定まるので、この $R$ を答えてください。
制約
- 入力はすべて整数
- $3 \le N \le 100$
- $P$ は凸多角形である
- $P$ の面積は正である
- $-10^6 \le X_i, Y_i \le 10^6$
- $(X_1, Y_1), \cdots, (X_N, Y_N)$ は $P$ の頂点を（ $x$ 軸の正の向きを右向き、 $y$ 軸の正の向きを上向きとしたときの）反時計回転で与えたものである。
- $(X_i, Y_i), (X_{i+1}, Y_{i+1}), (X_{i+2}, Y_{i+2})$ は一直線上に存在しない。ただし、 $(X_{N+1}, Y_{N+1})$ は $(X_1, Y_1)$ を表し、 $(X_{N+2}, Y_{N+2})$ は $(X_2, Y_2)$ を表す。 $(1 \le i \le N)$
入力
$N$ $X_1$ $Y_1$ $\vdots$ $X_N$ $Y_N$
出力
答えを出力せよ。サンプル
サンプル1
入力
3 1 1 0 2 -1 0
出力
499122178
多角形 $P$ は次のようになります：
多角形 $Q$ に含まれる確率が正である格子点は次の $4$ 点です。
- $(0,1)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a, b \lt 1, 2a-1 \lt b \lt \frac{a}{2}+\frac{1}{2}$ であり、確率は $\frac{1}{2}$ である
- $(0,2)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a \lt \frac{b}{2} \lt 1$ であり、確率は $\frac{1}{4}$ である
- $(1,1)$： $Q$ の内部に含まれる必要十分条件は $0 \lt b \lt \frac{a}{2} \lt 1$ であり、確率は $\frac{1}{4}$ である
- $(1,2)$： $Q$ の内部に含まれる必要十分条件は $0 \lt a, b \lt 1, 1 \lt a+b$ であり、確率は $\frac{1}{2}$ である
以上より、 $Q$ の内部に含まれる格子点の個数の期待値は $\frac{3}{2}$ であることが分かります。 $2 \times 499122178 \equiv 3 \pmod{998244353}$ であるため、 $499122178$ を出力します。
サンプル2
入力
13 541787 -802804 745984 -610628 821010 -469321 148557 920322 -276352 776016 -689247 481241 -955894 130548 -804935 -349606 -374167 -778760 -33915 -920255 5303 -921478 231589 -902268 348969 -873524
出力
68155167
多角形 $P$ は次のようになります：
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。