No.1144 Triangles

問題提出提出一覧質問統計解説

問題文テストジャッジコードジェネレータ

問題一覧 > 通常問題

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 :

null / テスター :

hotman78

2 ProblemId : 4687 / 出題時の順位表 / 自分の提出

問題文最終更新日: 2022-04-25 23:38:17

はじめに

C++ での余裕を持った正答は確認してますが、制約がきつめかもしれません。TL が 3 秒 であることに注意してください。

問題文

$n$ 個の点が与えられます。 $i$ 番目の点は $P_i(x_i, y_i)$ です。
$\displaystyle \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} 2 \times \triangle P_i P_j P_k$
を $(10^9 + 7)$ で割った余りを求めてください。ただし、 $\triangle ABC$ は点 $A, B, C$ を頂点とする三角形の面積とします。三角形が成立しない場合は $0$ とします。
この制約下で与えられた $N$ 点のうちどの $3$ つからなる三角形の面積の二倍も整数となることが示せます。

制約

$3 \le n \le 2 \times 10^3$
$-10^4 \le x_i, y_i \le 10^4$
入力はすべて整数

入力

 $n$ 
 $x_1\ y_1$ 
 $x_2\ y_2$ 
 $\dots$ 
 $x_n\ y_n$

出力

$\displaystyle \sum_{i=1}^{n} \sum_{j=i+1}^{n} \sum_{k=j+1}^{n} 2 \times \triangle P_i P_j P_k$
を $(10^9 + 7)$ で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1

入力

出力

$2 \times \triangle P_1 P_2 P_3 + 2 \times \triangle P_1 P_2 P_4 + 2 \times \triangle P_1 P_2 P_5 + 2 \times \triangle P_1 P_3 P_4 + 2 \times \triangle P_1 P_3 P_5 + 2 \times \triangle P_1 P_4 P_5 + 2 \times \triangle P_2 P_3 P_4 + 2 \times \triangle P_2 P_3 P_5 + 2 \times \triangle P_2 P_4 P_5 + 2 \times \triangle P_3 P_4 P_5 \\ 1+1+2+1+6+4+1+5+3+1=25$ です。

サンプル2

入力

出力

サンプル3

入力

出力

三点が同一直線状に存在することもあります。このケースではありませんが、二点以上が同じ点の場合もあります。

サンプル3

入力

10
3537 9451
9695 -7141
-3029 5335
400 5744
928 7006
-2302 -6741
-6467 -9447
3962 9075
3296 -3856
-3 7451

出力

233469265

$(10^9+7)$ で割った余りを出力することに注意してください。

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