Suns and Rays

题意翻译

**题目描述** 海狸喜欢画太阳，他们准备设计一个程序来处理他的画作。给你一张海理的画，画中有2种颜色：背景色：蓝色，太阳色：黄色。 你需要计算图像中太阳的数量，并计算每一个太阳的光线数量。太阳是任意旋转的带有光线的椭圆。光线是连接太阳边界上的点与太阳外的点的线段。 图一：所有太阳都是圆的。 图二：所有的太阳都是椭圆的，而且它们的轴与坐标轴平行。 图三：所有的太阳都是可以任意旋转的椭圆。 保证以下规则： - 两个太阳不会在一个点上 - 射线的宽度为3 - 太阳的坐标不小于40，且不大于200。 - 两条光线不会相交 - 光线的长度不小于10且不大于30 **输入格式** 第一行两个整数$h$，$w$(1$\leq$ $h$,$w$$\leq$ 1600) 分别表示这幅画的长和宽。 接下来的$h$行，每行$w$个整数，用空格分开，表示海狸的画。0代表背景色（蓝色），1代表太阳颜色（黄色） **输出格式** 第一行包含一个数字$k$,表示太阳的个数。第二行输出$k$个整数，对应每个太阳的射线数，必须按照升序输出。 本题分为三个子问题。 - 子问题1：输入的所有太阳都是圆形，30分。 - 子问题2：输入的所有的太阳都是椭圆的，而且它们的轴与坐标轴平行，40分。 - 子问题3：所有的太阳都是可以任意旋转的椭圆，30分。 本题翻译由@[_tommysun_](https://www.luogu.com.cn/user/203452) 提供。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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.

输入输出样例

暂无测试点

说明

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.