← 返回题目列表

Codeforces · 316/F2

F2. 太阳和光线

中文机器翻译题面 查看原题

聪明的海狸对绘画产生了兴趣。他画太阳。然而,在某个时候,聪明的海狸意识到仅仅画太阳是很无聊的。因此,他决定设计一个程序来处理他的绘图。你会得到一张海狸画的图画。它将有两种颜色:一种用于背景,一种用于图像中的太阳。您的任务是计算图像中太阳的数量,并计算每个太阳的光线数量。

太阳是带有射线的任意旋转的椭圆。射线是连接椭圆边界上​​的点与椭圆外某点的线段。

所有太阳都是圆形的图像。

所有太阳都是椭圆形的图像,它们的轴与坐标轴平行。

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

保证:

- 没有两个太阳有共同点。
- 光线的宽度为 3 像素。
- 椭圆太阳轴的长度将在 40 到 200 像素之间。
- 没有两条光线相交。
- 所有光线的长度都在 10 到 30 像素之间。

输入

第一行包含两个整数 h 和 w — 图像的高度和宽度 (1 ≤ h, w ≤ 1600)。接下来的 h 行每行将包含 w 个空格分隔的整数。他们描述了聪明海狸的照片。每个数字等于 0(图像背景)或 1(太阳颜色)。

得分 30 分的输入限制为(子问题 F1):

- 图像上的所有太阳都是圆形。

得分 70 分的输入限制为(子问题 F1+F2):

- 图像上的所有太阳都是椭圆形,其轴与坐标轴平行。

获得 100 分的输入限制为(子问题 F1+F2+F3):

- 图像上的所有太阳都是椭圆形,它们可以任意旋转。

输出

第一行必须包含一个数字 k — 海狸图像上的太阳数量。第二行必须恰好包含 k 个空格分隔的整数,对应于每个太阳的光线数量。第二行的数字必须按升序排列。

注意

对于每个复杂级别,我们都会建议您在初始数据中使用一个样本。您可以从 http://www.abbyy.ru/sun.zip 下载示例。