問題一覧 > 通常問題

No.2769 Number of Rhombi

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 65
作問者 : srjywrdnprktsrjywrdnprkt / テスター : 👑 hahhohahho
0 ProblemId : 10521 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2024-05-31 23:42:59

問題文

$2$ 次元平面上に相異なる $N$ 個の点があります。$i$ 番目の点の座標は $(x_i, y_i)$ です。

これらの点から相異なる $4$ つの点を選んで作ることのできる四角形のうち、ひし形であるものの数を求めてください。

入力

$N$
$x_1\ y_1$
$\vdots$
$x_N\ y_N$

入力は全て整数で以下の制約を満たす。

  • $4 \leq N \leq 1000$
  • $-10^9 \leq x_i \leq 10^9$
  • $-10^9 \leq y_i \leq 10^9$
  • $i\neq j$ ならば $(x_i, y_i) \neq (x_j, y_j)$

出力

$N$ 個の点から相異なる $4$ つの点を選んで作ることのできる四角形のうち、ひし形であるものの数を出力してください。最後に改行してください。

サンプル

サンプル1
入力
9
0 0
0 1
0 2
1 0
1 1
1 2
2 0
2 1
2 2
出力
6

$i$ 番目の点を点 $i$ と表すとき、以下の $6$ 種類のひし形ができます。

  1. 点 $1, 2, 4, 5$ を反時計回りに結んで作られるひし形
  2. 点 $2, 3, 5, 6$ を反時計回りに結んで作られるひし形
  3. 点 $4, 5, 7, 8$ を反時計回りに結んで作られるひし形
  4. 点 $5, 6, 8, 9$ を反時計回りに結んで作られるひし形
  5. 点 $1, 3, 7, 9$ を反時計回りに結んで作られるひし形
  6. 点 $2, 6, 8, 4$ を反時計回りに結んで作られるひし形

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

条件を満たす点の選び方が存在しないこともあります。

サンプル3
入力
16
0 0
0 1
0 2
0 3
1 0
1 1
1 2
1 3
2 0
2 1
2 2
2 3
3 0
3 1
3 2
3 3
出力
22

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