Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
Максимальный балл: | 100 |
Юный программист Вася решил разработать собственную платформу виртуальной реальности. Для начала он реализовал вывод пустой чёрной сцены с единственным красным шаром. Однако в алгоритме вывода шара Вася допустил ошибки, из-за которых шар не всегда выводился правильно.
Для отладки Вася сделал скриншоты своего приложения (шар на них должен
превратиться в круг). Скриншот представлен прямоугольным массивом символов,
в котором символ "#
" представляет красный пиксель,
а символ ".
" — чёрный пиксель.
Если шар нарисован правильно, то красными будут только те пиксели, координаты которых (x;y) удовлетворяют условию (x−x0)2+(y−y0)2≤r2, где x0, y0, r — неизвестные целые числа.
Требуется написать программу, которая по изображению выяснит, правильно ли на нём нарисован шар (спроецированный в круг), и если да, то определит значения x0, y0, r.
Первая строка входных данных содержит целые числа X Y — ширину и высоту прямоугольника.
Следующие Y строк содержат по X символов "#
" и ".
" каждая —
описание изображения.
Выходные данные должны содержать целые числа 1x0y0r, если изображение является правильным, и число 0 в противном случае. Координаты отсчитываются от верхнего левого угла.
3≤X,Y≤2000, r≥1
1≤x0−r<x0+r≤X, 1≤y0−r<y0+r≤Y
№ | Стандартный вход | Стандартный выход |
---|---|---|
1 |
|
|
Поскольку правильное изображение содержит ровно один круг, то ограничивающий прямоугольник всех красных пикселей на изображении должен совпадать с ограничивающим прямоугольником круга.
Таким образом, следует найти ограничивающий прямоугольник (то есть найти минимальные и максимальные координаты красных пикселей по каждой оси), проверить, что он является квадратом с нечётной длиной стороны, найти потенциальный центр круга как центр ограничивающего квадрата. Затем следует проверить, что внутри квадрата красными являются те и только те пиксели, которые удовлетворяют условию (x−x0)2+(y−y0)2≤r2.