Генератор случайных карт известной игры Heroes of Might and Magic III создает острова, на которых изначально будут расположены герои. При такой генерации острова получаются различными по величине. Назовем коэффициентом несправедливости отношение площади наибольшего острова к площади наименьшего. Требуется определить этот коэффициент.

Карта задается прямоугольником N × M, в каждой клетке которого записана цифра 0 (вода) или цифра 1 (земля). Островом считается максимальное связное множество клеток, содержащих единички, т.е. такое множество клеток A, что:
    из любой клетки A можно пройти до любой другой клетки A, переходя лишь через клетки A и их стороны;
    при добавлении к A любой другой клетки, содержащей 1, предыдущее условие нарушается.

Входные данные
В первой строке входного файла содержатся числа N и M – размеры карты (1 ≤ N, M ≤ 1000). Далее записана сама карта – M строк по N чисел (0 или 1) в каждой. Числа внутри строки разделяются пробелом.

Выходные данные
В выходной файл вывести коэффициент несправедливости с 5 знаками после десятичной точки. Если на карте нет ни одного острова, вывести 0.

Пример входного файла
7 6
1 1 0 0 0 0 0
0 1 0 1 0 0 0
1 1 0 1 1 0 0
1 0 0 0 1 0 0
0 0 0 1 1 1 0
1 1 1 0 0 1 0

Пример выходного файла
2.66667

   Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 103]      

Две высоты треугольника равны 12 и 20. Докажите, что третья высота меньше 30.

Прислать комментарий

Решение

Дан ABC и точка D внутри него, причем AC - DA > 1 и BC - BD > 1. Берётся произвольная точка E внутри отрезка AB. Доказать, что EC - ED > 1.

Прислать комментарий

Решение

Точки  C₁, A₁, B₁ взяты на сторонах AB, BC, CA треугольника ABC так, что  BA₁ = ^. BC, CB₁ = ^. CA, AC₁ = ^. AB, причем  1/2 < < 1. Докажите, что периметр P треугольника ABC и периметр P₁ треугольника A₁B₁C₁ связаны неравенствами  (2-1)P < P₁ < P.

Прислать комментарий

Решение

а) Докажите, что при переходе от невыпуклого многоугольника к его выпуклой оболочке периметр уменьшается. (Выпуклой оболочкой многоугольника называют наименьший выпуклый многоугольник, его содержащий.)
б) Внутри выпуклого многоугольника лежит другой выпуклый многоугольник. Докажите, что периметр внешнего многоугольника не меньше, чем периметр внутреннего.

Прислать комментарий

Решение

Внутри треугольника ABC периметра P взята точка O. Докажите, что  P/2 < AO + BO + CO < P.

Прислать комментарий

Решение

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 103]