P5198 [USACO19JAN] Icy Perimeter S

The second Silver problem of the USACO January contest.

Farmer John is going to start his ice cream business. He built a machine that produces scoops of ice cream, but unfortunately their shapes are not very regular. He now wants to improve the machine so that the ice cream scoops it produces have more reasonable shapes. The shape of the ice cream produced by the machine can be represented by an $N \times N$ ($1 \leq N \leq 1000$) grid pattern, for example: ``` ##.... ....#. .#..#. .##### ...### ....## ``` Each `.` character represents an empty area, and each `#` character represents a $1 \times 1$ square cell of ice cream. Unfortunately, the machine may produce several ice cream scoops that are not connected to each other (there are two in the picture above). An ice cream scoop is connected if every ice cream square cell in it can be reached from any other ice cream cell in the same scoop by repeatedly moving to an adjacent ice cream cell to the east, south, west, or north. Farmer John wants to find the area and perimeter of the ice cream scoop with the largest area. The area of a scoop is the number of `#` cells in it. If multiple scoops are tied for the largest area, he wants the perimeter of the one with the smallest perimeter among them. In the picture above, the smaller scoop has area $2$ and perimeter $6$, and the larger scoop has area $13$ and perimeter $22$. Note that a scoop may have “holes” in the middle (empty regions surrounded by ice cream). In that case, the boundary of the holes is also counted in the scoop’s perimeter. A scoop may also appear inside a region surrounded by another scoop; in this case, they are considered different scoops. For example, the following case contains a scoop of area $1$, surrounded by a scoop of area $16$: ``` ##### #...# #.#.# #...# ##### ``` It is important to compute both the area and the perimeter of a scoop, because Farmer John ultimately wants to minimize the ratio of perimeter to area, which he calls the “ice peri rate”. When this ratio is smaller, the ice cream melts more slowly, because the surface area per unit mass is smaller.

The first line contains $N$. The next $N$ lines describe the machine’s output. There is at least one `#` character.

Output one line containing two integers separated by a space: the first is the maximum scoop area, and the second is its perimeter. If multiple scoops are tied for the maximum area, output the one with the smallest perimeter.

Translated by ChatGPT 5