Eng yaqin nuqtalar

Son o'qida $n$ ta turli nuqta berilgan. Ikki nuqta orasidagi eng kichik masofani va shu masofada joylashgan nuqtalar juftliklari sonini toping. $x$ va $y$ nuqtalar orasidagi masofa $|x - y|$ ga teng.

Birinchi qatorda $n$ ($2 \le n \le 10^5$). Ikkinchi qatorda $n$ ta turli butun son $x_1, \ldots, x_n$ ($|x_i| \le 2 \cdot 10^9$) — nuqtalar koordinatalari.

Bitta qatorda ikkita son: eng kichik masofa va shunday masofadagi juftliklar soni.

Barcha juftliklarni tekshirish $O(n^2)$ — $n = 10^5$ da $5 \cdot 10^9$ amal. Nuqtalarni saralang: eng yaqin nuqta albatta saralangan massivdagi qo'shni bo'ladi, shuning uchun faqat $x_{i+1} - x_i$ farqlarni ko'rish yetarli.

Masofa $4 \cdot 10^9$ gacha yetadi va 32 bitli int ga sig'maydi: birinchi misolda 2 3, nuqtalar -2000000000 va 2000000000 bo'lsa javob 4000000000 1.

Manba: acmp.ru, 344-masala.