問題一覧 > 通常問題

No.1447 Greedy MtSaka

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 93
作問者 : MtSakaMtSaka / テスター : butsurizukibutsurizuki
5 ProblemId : 6081 / 出題時の順位表
問題文最終更新日: 2021-04-01 19:18:01

問題文

MtSaka くんはいま領土争いをしています。そこで彼は $N$ 個の点を占領することができました。
彼はそれらの点を結んでできる $N$ 角形内を支配します。
$N$ 個の点すべての座標が与えられるので、支配する面積の $2$ 倍を求めてください。
但し、答えは常に整数となります。また、入力で与えられた順に結んでできる多角形は凸多角形であり、反時計回りに与えられることが保証されます。

入力

$N$
$X_1\ Y_1$
$X_2\ Y_2$
$\vdots$
$X_N\ Y_N$

制約

・$3 \leq N \leq 30$
・$-10000 \leq X_i,Y_i \leq 10000 (1 \leq i \leq N)$
・入力はすべて整数である
・入力は問題文の条件を満たす

出力

MtSaka くんが支配する $N$ 角形の面積の $2$ 倍を、ひとつの正整数として1行に出力してください。 最後に改行してください。

サンプル

サンプル1
入力
3
1 0
1 1
0 1
出力
1

狭すぎません?

サンプル2
入力
7
-1 -1
2 -1
2 3
1 5
0 6
-1 5
-2 3
出力
42

サンプル3
入力
6
4 1
9 1
11 4
9 9
7 8
5 5
出力
72

複雑な形ですね...

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。