Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2024

2020-2022 2023 Regulations Schedule RODO info Ranking

Problem description


Prostsze dwa koła
(dwa-kola-easy)
Limit pamięci: 32 MB
Limit czasu: 0.50 s

Dość dawno temu (przy okazji sparingu ósmego) Jasio umieszczał dwa koła wewnątrz wielokąta wypukłego. Niestety, nikt nie był w stanie mu pomóc z tym zadaniem. Dlatego Jasio zajmuje się teraz łatwiejszym problemem, aby znowu mógł Cię poprosić o pomoc.

Ponownie Jasio umieszcza dwa koła, jednak tym razem wewnątrz prostokąta. Jasio nie pyta jak umieścić w prostokącie te koła, on już je umieścił. Co więcej, zrobił to nawet dobrze: koła nie przecinają się, ani nawet nie dotykają. Jasio pokazał Ci swoje dzieło w formie ASCII arta. Czy potrafisz powiedzieć mu jakie są współrzędne środków jego kół? Możesz założyć, że wszystkie te wartości są całkowite tak samo jak promienie kół.

Napisz program, który: wczyta rysunek Jasia zawierający dwa koła, wyznaczy współrzędne środków oraz promienie kół i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N oraz M określające liczbę wierszy oraz kolumn rysunku Jasia. Kolejne N wierszy zawiera po M znaków . (kropka) lub # (hasz). Znak # (hasz) reprezentuje punkt kratowy należący do koła, zaś . (kropka) reprezentuje punkt kratowy poza kołem.

Współrzędne x (odcięte) układu rosną od lewej do prawej od 0 do M − 1 włącznie. Współrzędne y (rzędne) układu rosną od dołu do góry od 0 do N − 1 włącznie.

Wyjście

Program powinien wypisać dwa wiersze. Każdy ma zawierać informacje o jednym z kół na rysunku Jasia. Opis każdego koła ma składać się z dwóch liczb naturalnych xi, yi oddzielonych pojedynczym odstępem. Mają to być współrzędne (xi,yi) środka i-tego koła.

Kolejność wypisywania punktów może być dowolna.

Ograniczenia

1 ≤ N, M ≤ 1 000.

Przykład

Wejście Wyjście
15 17
.................
.................
...........#.....
.........#####...
.........#####...
........#######..
....#....#####...
..#####..#####...
.#######...#.....
.#######.........
#########........
.#######.........
.#######.........
..#####..........
....#............
11 9
4 4