問題一覧 > 通常問題

No.1144 Triangles

レベル : / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 37
作問者 : 👑 nullnull / テスター : hotmanwwhotmanww
2 ProblemId : 4687 / 出題時の順位表
問題文最終更新日: 2020-07-31 03:46:51

はじめに

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
入力
5
0 0
1 1
3 4
2 3
0 2
出力
25


$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
0 0
0 1
2 0
出力
2

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

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

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。