CF178E3.The Beaver's Problem - 2

Offering the ABBYY Cup participants a problem written by the Smart Beaver is becoming a tradition. He proposed the following problem.

You are given a monochrome image, that is, an image that is composed of two colors (black and white). The image is given in raster form, that is, as a matrix of pixels' colors, and the matrix's size coincides with the size of the image.

The white color on the given image corresponds to the background. Also, the image contains several black geometric shapes. It is known that the image can contain only two types of shapes: squares and circles. Your task is to count the number of circles and the number of squares which the given image contains.

The squares on the image can be rotated arbitrarily. In addition, the image can possibly contain some noise arranged as follows: each pixel of the original image can change its color to the opposite with the probability of 20%.

An example of an image that has no noise and the sides of the squares are parallel to the coordinate axes (two circles and three squares).

An example of an image that has no noise and the squares are rotated arbitrarily (two circles and three squares).

An example of an image that has noise and the squares are rotated arbitrarily (one circle and three squares).

为 ABBYY 杯参赛者提供一道由“聪明的海狸”（Smart Beaver）编写的题目，已成为一项传统。他提出了如下问题。

给定一幅单色图像，即仅由两种颜色（黑色与白色）构成的图像。该图像以光栅形式给出，也就是以像素颜色矩阵的形式表示，且该矩阵的尺寸与图像的实际尺寸一致。

图像中的白色对应背景。此外，图像中还包含若干黑色几何图形。已知图像中仅可能出现两类图形：正方形与圆形。你的任务是统计该图像中所含的圆形数量与正方形数量。

图像中的正方形可以任意旋转。此外，图像中可能含有噪声，其生成方式如下：原始图像中的每个像素均以 $20\%$ 的概率将其颜色反转（即黑变白、白变黑）。

一幅无噪声图像示例，其中正方形的边与坐标轴平行（含两个圆形和三个正方形）。

一幅无噪声图像示例，其中正方形被任意旋转（含两个圆形和三个正方形）。

一幅含噪声图像示例，其中正方形被任意旋转（含一个圆形和三个正方形）。

The first input line contains a single integer n (1000 ≤ n ≤ 2000), which is the length and the width of the original image.

Next n lines describe the matrix of colors of the image pixels. The i-th line contains exactly n integers a__ij (0 ≤ a__ij ≤ 1), separated by spaces. Value of a__ij = 0 corresponds to a white pixel and a__ij = 1 corresponds to a black one.

It is guaranteed that the lengths of the sides of the squares and the diameters of the circles in the image are at least 15 pixels, and the distance between any two figures is at least 10 pixels. It is also guaranteed that a human can easily calculate the number of circles and squares in the original image. The total number of figures in the image doesn't exceed 50.

The input limitations for getting 20 points are:

• These test cases have no noise and the sides of the squares are parallel to the coordinate axes.

The input limitations for getting 50 points are:

• These test cases have no noise, but the squares are rotated arbitrarily.

The input limitations for getting 100 points are:

• These test cases have noise and the squares are rotated arbitrarily.

第一行输入包含一个整数 $n$（$1000 \leq n \leq 2000$），表示原始图像的长和宽。

接下来的 $n$ 行描述图像像素的颜色矩阵。第 $i$ 行恰好包含 $n$ 个整数 $a_{ij}$（$0 \leq a_{ij} \leq 1$），以空格分隔。其中 $a_{ij} = 0$ 表示白色像素，$a_{ij} = 1$ 表示黑色像素。

保证图像中正方形的边长与圆形的直径均至少为 15 像素，且任意两个图形之间的距离至少为 10 像素。同时保证人类可以轻松地计算出原始图像中圆和正方形的总数。图像中图形的总数不超过 50。

获得 20 分的输入限制为：

• 这些测试用例不含噪声，且正方形的边与坐标轴平行。

获得 50 分的输入限制为：

• 这些测试用例不含噪声，但正方形可任意旋转。

获得 100 分的输入限制为：

• 这些测试用例含噪声，且正方形可任意旋转。

Print exactly two integers, separated by a single space — the number of circles and the number of squares in the given image, correspondingly.

准确输出两个整数，用一个空格分隔——分别为给定图像中圆的数量和正方形的数量。

You are given a sample of original data for each difficulty level. The samples are available at http://codeforces.com/static/materials/contests/178/e-samples.zip .

每个难度级别都提供了一份原始数据样本。样本文件位于 http://codeforces.com/static/materials/contests/178/e-samples.zip 。