300953: CF178E3. The Beaver's Problem - 2

Memory Limit:256 MB Time Limit:5 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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 $ %. ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF178E3/575cc300a436bc791f059ed1604954db020e4792.png) 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). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF178E3/5a255ee1bca061f5ff62a305107ac74540469a88.png) An example of an image that has no noise and the squares are rotated arbitrarily (two circles and three squares). ![](https://cdn.luogu.com.cn/upload/vjudge_pic/CF178E3/6588309d80aee82245c95133dff3b167b5dbc7e6.png) An example of an image that has noise and the squares are rotated arbitrarily (one circle and three squares).

输入输出格式

输入格式


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.

输出格式


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.ru/static/materials/contests/178/e-samples.zip .

Input

题意翻译

本题与 [CF178E1](https://www.luogu.com.cn/problem/CF178E1) 和 [CF178E2](https://www.luogu.com.cn/problem/CF178E3) 的唯一区别在于图像的质量。 ### 简要题意 给出一张黑白图像,求出图中圆形和方形的数量。 - 图像大小 $n$ 给定; - 图像背景为白色,在输入中用 `0` 表示; - 图形均为黑色,在输入中用 `1` 表示; - 图像中可能存在噪声,如果存在,则对于每个原图中的像素,都有 $20\%$ 的概率转变为相反的颜色; - 正方形可能会被任意旋转; - 输出一行用空格隔开的两个数,即圆的数量和方的数量。 ### 数据范围 - 对于本题的数据,没有任何其他限制; - 对于所有的数据,保证 $1000 \le n \le 2000$,圆的直径和正方形的边长大于 $15$ 个像素,每两个图形间至少有 $10$ 像素的间距。 Translate by [shiyihang](https://www.luogu.com.cn/user/221855).

加入题单

上一题 下一题 算法标签: