标题:发一道题,大家帮忙想想
只看楼主
葬烟
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2008-9-3
得分:0 
你上面那个图不合乎规格阿,缺了5个个直角三角形。按照规则,匹配上一个直角的图形就是矩形的一角,所有能够匹配直角的图形不能超过4个。
  另外你的原题中:
  If pairs of consecutive *s on a common horizontal edge of a piece are stored in columns c1
and c2 , then jc1 􀀀 c2j = 2.
 If pairs of consecutive *s on a common vertical edge of a piece are stored in rows r1 and r2,
then jr1 􀀀 r2j = 1.
 If pairs of consecutive *s on a common diagonal edge of a piece are stored in rows r1 and r2
and in columns c1 and c2 , then jr1 􀀀 r2j = 1 and jc1 􀀀 c2j = 1.
 No piece contains any hole.

 Say that a * stored in row r1 and column c1 is a neighbouring * of a * stored in row r2 and
column c2 if either c1 = c2 and jr1 􀀀 r2j = 1, or r1 = r2 and jc1 􀀀 c2j = 2, or jr1 􀀀 r2j = 1
and jc1 􀀀 c2j = 1. The vertices of a given piece can be identi ed as those points marked
with a * from which it is possible to reach neighbouring *s in exactly two d erent directions
and in no opposite direction.

  这段将边规则的,里面好多乱码,给个清楚点的吧。你那个关于是不是合格三角形的问题,答案可能估计就在里面。
2008-09-16 20:42
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
得分:0 
发了题目之后发现没有反应就一直没有来。。。结果发现大家还是注意到了。。。

题目条件说了角不会被切开
还有顶点不会有3邻居(或以上)
还有直角都会被保留,
还有,如果长和宽至少一个是只有两块碎片就可以拼成了,

所以只要找到外部直角(注意:内部也有直角,看输入文件3),然后把直角边相加,上边和上边加,下边加下边,左右也是这样,然后比较长的就是拼成的矩形边了


所以题目就简化了很多

刚拿到手时觉得比较困难,仔细读题目了之后还是发现不难实现的

比较难的面积计算有人用海伦公式,不过我认为我之前说的矢量算法应该是最简单的了

我用数组做的,代码长度200多行
2008-09-21 18:16



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-232036-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.217223 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved