No.1144 Triangles
タグ : / 解いたユーザー数 46
作問者 :
null
/ テスター :
hotman78
はじめに
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もしくは右上の雲マークをクリックしてアカウントを作成してください。