Граф на площині#12959

Граф на площині

4 секунди
512 мегабайтів
Складна

Вам задано різних точок (x_i, y_i) на двовимірній площині.

Неорієнтований зважений граф з дійсними вагами називається хорошим, якщо виконуються такі умови.

Знайдіть мінімальну кількість ребер у хорошому графі.

Вхідні дані

У першому рядку задано ціле число – кількість точок.

У наступних рядках задано два цілих числа x_i та y_i – координати точок.

1 \le n \le 2000,

|x_i|, |y_i| \le 10^9.

Всі точки різні.

Вихідні дані

Виведіть одне ціле число – мінімальну кількість ребер у хорошому графі.

Приклади

Приклад

Loading
Loading

Приклад 1

Loading
Loading

Примітка

У першому прикладі мінімальна кількість ребер у хорошому графі — шість.

У другому прикладі мінімальна кількість ребер у хорошому графі — вісім.