No.2769 Number of Rhombi
タグ : / 解いたユーザー数 64
作問者 :
srjywrdnprkt
/ テスター :
hahho
Problem Statement
There are $N$ distinct points on a $2$-dimensional plane. The coordinates of the $i$-th point are $(x_i, y_i)$.
Among the quadrilaterals that can be formed by choosing $4$ distinct points from these points, find the number of those that are rhombi.
Input
$N$ $x_1\ y_1$ $\vdots$ $x_N\ y_N$
All inputs are integers and satisfy the following constraints.
- $4 \leq N \leq 1000$
- $-10^9 \leq x_i \leq 10^9$
- $-10^9 \leq y_i \leq 10^9$
- If $i\neq j$, then $(x_i, y_i) \neq (x_j, y_j)$
Output
Output the number of rhombi among the quadrilaterals that can be formed by choosing $4$ distinct points from the $N$ points. Print a newline at the end.
Sample
Sample 1
Input
9 0 0 0 1 0 2 1 0 1 1 1 2 2 0 2 1 2 2
Output
6
Denoting the $i$-th point as point $i$, the following $6$ rhombi can be formed.
- The rhombus formed by connecting points $1, 2, 4, 5$ counterclockwise
- The rhombus formed by connecting points $2, 3, 5, 6$ counterclockwise
- The rhombus formed by connecting points $4, 5, 7, 8$ counterclockwise
- The rhombus formed by connecting points $5, 6, 8, 9$ counterclockwise
- The rhombus formed by connecting points $1, 3, 7, 9$ counterclockwise
- The rhombus formed by connecting points $2, 6, 8, 4$ counterclockwise
Sample 2
Input
4 0 0 0 1 2 0 2 1
Output
0
There may be no way to choose points that satisfies the condition.
Sample 3
Input
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
Output
22
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。