CF316F2.Suns and Rays

Smart Beaver became interested in drawing. He draws suns. However, at some point, Smart Beaver realized that simply drawing suns is boring. So he decided to design a program that will process his drawings. You are given a picture drawn by the beaver. It will have two colors: one for the background and one for the suns in the image. Your task will be to count the number of suns in the image and for each of them to count the number of rays.

Sun is arbitrarily rotated ellipse with rays. Ray is a segment which connects point on boundary of the ellipse with some point outside ellipse.

An image where all suns are circles.

An image where all suns are ellipses, their axes are parallel to the coordinate axes.

An image where all suns are rotated ellipses.

It is guaranteed that:

• No two suns have common points.
• The rays’ width is 3 pixels.
• The lengths of the ellipsis suns’ axes will lie between 40 and 200 pixels.
• No two rays intersect.
• The lengths of all rays will lie between 10 and 30 pixels.

聪明的海狸对绘画产生了兴趣。他画太阳。然而，某一天，聪明的海狸意识到单纯地画太阳十分枯燥。于是他决定设计一个程序来处理自己的画作。你将得到一幅由海狸绘制的图像。该图像仅包含两种颜色：一种用于背景，另一种用于图像中的太阳。你的任务是统计图像中太阳的数量，并对每一个太阳统计其射线（rays）的数量。

太阳是一个任意旋转的椭圆，其上附有若干射线。每条射线是一条线段，它的一个端点位于椭圆边界上，另一个端点位于椭圆外部。

所有太阳均为圆形的图像。

所有太阳均为椭圆，且其主轴与坐标轴平行的图像。

所有太阳均为旋转椭圆的图像。

保证满足以下条件：

• 任意两个太阳之间无公共点；
• 射线的宽度为 3 像素；
• 椭圆型太阳的半轴长度均在 40 至 200 像素之间；
• 任意两条射线互不相交；
• 所有射线的长度均在 10 至 30 像素之间。

The first line contains two integers h and w — the height and width of the image (1 ≤ h, w ≤ 1600). Next h lines will contain w space-separated integers each. They describe Smart Beaver’s picture. Each number equals either a 0 (the image background), or a 1 (the sun color).

The input limits for scoring 30 points are (subproblem F1):

• All suns on the image are circles.

The input limits for scoring 70 points are (subproblems F1+F2):

• All suns on the image are ellipses with axes parallel to the coordinate axes.

The input limits for scoring 100 points are (subproblems F1+F2+F3):

• All suns on the image are ellipses, they can be arbitrarily rotated.

第一行包含两个整数 $h$ 和 $w$ —— 图像的高度与宽度（$1 \le h,\,w \le 1600$）。接下来的 $h$ 行，每行包含 $w$ 个以空格分隔的整数，描述 Smart Beaver 的图像。每个数字为 $0$（图像背景）或 $1$（太阳的颜色）。

得分为 30 分的输入限制（子问题 F1）：

• 图像中所有太阳均为圆形。

得分为 70 分的输入限制（子问题 F1 + F2）：

• 图像中所有太阳均为椭圆，且其主轴与坐标轴平行。

得分为 100 分的输入限制（子问题 F1 + F2 + F3）：

• 图像中所有太阳均为椭圆，且可任意旋转。

The first line must contain a single number k — the number of suns on the beaver’s image. The second line must contain exactly k space-separated integers, corresponding to the number of rays on each sun. The numbers of the second line must be sorted in the increasing order.

第一行必须包含一个整数 $k$ —— 海狸图像中太阳的数量。
第二行必须恰好包含 $k$ 个以空格分隔的整数，分别表示每个太阳的射线数量。第二行中的数字必须按升序排列。

For each complexity level you are suggested a sample in the initial data. You can download the samples at http://www.abbyy.ru/sun.zip.

针对每个复杂度级别，初始数据中均提供了一个示例。您可从 http://www.abbyy.ru/sun.zip 下载这些示例。