Skip to content

一个算法问题

在一个直角坐标系的第一象限有面积为100*100的区域,即(0,0)(100,0)(100,100)(0,100)四个点围成的正方形区域.
输入一个多边形的顶点坐标集合(顺时针过逆时针方向).已知多边形是规则的,即其边沿着网格虚线,不会横穿单元格.比如:一个矩形(2,1)(2,3)(6,3)(6,1)

image001

之后会在此坐标系中,不断输入一个规则的多边形,比如继续输入一个十二边形(7,1)(7,6)(2,6)(2,10)(7,10)(7,15)(11,15)(11,10)(16,10)(16,6)(11,6)(11,1)

image004

对每次输入的图形,判断:

1.是否有顶点与已存在的图形顶点重叠.

2.是否有边与已存在的边重叠.

3.如果面积与已存在的面积重叠,或图形超越所定义的100*100区域,则退出程序.

输入的数据格式可自行定义,能够表示图形顶点坐标即可,算法语言自行选择,伪代码也可.

提示:

1.问题1较为简单,用集合(set)可解.

2.规则图形坐标点输入有规律,即输入的相邻两点x或y值相同.

3.问题3确保了判断问题1和2过程中不用考虑面积重叠情况.简化了算法复杂度.

Published inThinking

Be First to Comment

发表评论

电子邮件地址不会被公开。 必填项已用*标注