网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
[GZOI2011]涂颜色
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | border.in | 输出文件 | border.out |
题目描述:
你试图在直多边形(一个边都以90度或270度相交,而且内部没有洞的多边形)的基础上,一层层地增加新边框,在新的边框多围出来的区域涂上不同的颜色,以取得特殊的装饰效果。增加的边框与上一层增加的边框(第一层边框则是与直多边形的边)的距离都保持一个固定值d,如下图所示:
图3 装饰效果示例
在图3左的例子,在直多边形(灰色)的基础上加了两层边框,图3右的例子直多边形形状更复杂些,增加的边框离断成了两部分。注意边框也许离断成若干部分但绝不相交或重叠,即不会发生以下情况:
图4 不会发生的情况
你的任务是计算每层增加的边框长度及每层边框多围出来的面积。
输入格式(Border.in):
第一行是用空格分隔的三个正整数n,m,d。n是直多边形的边数,m是需要增加边框的层数,n<=100,m<=20,d是边框之间的距离。接下来的若干行,以顺时针方向描述直多边形的n个顶点坐标,每个坐标含空格分隔的两个正整数x和y。第一个顶点坐标满足y坐标最大;如果有多个满足此要求的顶点,我们从当中x坐标最小的开始。
输出格式(Border.out):
第一行包含m个整数,按次序输出每层增加的边框长度。
第二行包含m个整数,按次序输出每层边框多围出来的面积。
样例
Border.in |
Border.out |
6 2 10 |
340 420 |
10 1 7 |
380 |