eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Трикутник

Трикутник

На площині розміщено \textbf{N} (\textbf{3} ≤ \textbf{N}) точок. Серед них випадковим чином вибираються три точки, які потім з'єднуються відрізками. Потрібно визначити математичне очікування периметра отриманого трикутника, при умові, що кожна множина з трьох точок може бути вибрана з однаковою ймовірністю, а отриманий трикутник може бути виродженим. \InputFile У першому рядку вхідного файлу знаходяться два числа \textbf{H} і \textbf{W} (\textbf{1} ≤ \textbf{H}, \textbf{W} ≤ \textbf{700}). Далі йде рядків по \textbf{H} символів. \textbf{j}-й символ \textbf{i}-ого рядка дорівнює '\textbf{1}', якщо є точка з координатами (\textbf{i}, \textbf{j}), інакше у відповідній позиції стоїть символ '\textbf{0}'. Гарантується, що у вхідних даних подано як мінімум три точки. \OutputFile У вихідний файл виведіть одне число --- математичне очікування периметра отриманого трикутника. Відповідь повинна відрізнятись від вірної не більше, ніж на \textbf{10^\{-6\}}.
Ліміт часу 6 секунд
Ліміт використання пам'яті 256 MiB
Вхідні дані #1
11 20
10000000001000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
00000000000000000000
10000000000000000000
Вихідні дані #1
34.142135624
Автор Дмитро Жуков
Джерело Зимова Школа, Харків 2011, День 2