問題一覧 > 通常問題

No.2769 Number of Rhombi

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

問題文

22 次元平面上に相異なる NN 個の点があります。ii 番目の点の座標は (xi,yi)(x_i, y_i) です。

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

入力

NN
x1 y1x_1\ y_1
\vdots
xN yNx_N\ y_N

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

  • 4N10004 \leq N \leq 1000
  • 109xi109-10^9 \leq x_i \leq 10^9
  • 109yi109-10^9 \leq y_i \leq 10^9
  • iji\neq j ならば (xi,yi)(xj,yj)(x_i, y_i) \neq (x_j, y_j)

出力

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

サンプル

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

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

  1. 1,2,4,51, 2, 4, 5 を反時計回りに結んで作られるひし形
  2. 2,3,5,62, 3, 5, 6 を反時計回りに結んで作られるひし形
  3. 4,5,7,84, 5, 7, 8 を反時計回りに結んで作られるひし形
  4. 5,6,8,95, 6, 8, 9 を反時計回りに結んで作られるひし形
  5. 1,3,7,91, 3, 7, 9 を反時計回りに結んで作られるひし形
  6. 2,6,8,42, 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もしくは右上の雲マークをクリックしてアカウントを作成してください。