| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 2269 人关注过本帖
标题:发一道题,大家帮忙想想
只看楼主 加入收藏
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
     
aa
阿谢谢楼上几位帮忙想,关于不规则图形计算,我想到了一个好方法,就是把不规则图形的顶点坐标记录下来,然后顺时针取点(逆时针也行,一个方向就行),绕图形一周,按照矢量算法,把所有边和坐标抽组成的梯形面积加起来(有正有负),就是不规则图形面积了,楼上的说到的星星个数的算法我也想过,可是在求和的时候总会出现一些差错,因为那种算法把没有把边当成理想边,就是说边也有厚度,但是图形组合拼起来的时候,边是合并的,所以会出现差错,只能把边当成无厚度的理想边才好算一些

另外关于矩形面积的计算,因为是英文版的题目,所以没看清楚意思。。。对不起大家了,后来发现了一个条件,就是不规则图形切割后不会乱摆,不会旋转,直角不会被切断,而且对于边来说,长和宽至少有一侧是只有两块不规则图形拼起来的,有了这两个条件,我根据直角边来计算矩形的长宽还是比较容易了

感谢大家的讨论,呵呵,我是新人,发现这个论坛很好很强大,我把题目贴在这里,如果你们有兴趣可以做一做,这是国外大学的assignment
2008-09-12 01:31
xyzx
Rank: 1
等 级:新手上路
帖 子:9
专家分:0
注 册:2008-9-12
收藏
得分:0 
支持,真厉害
2008-09-12 01:51
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
General description: Your program will read data from a data le that:
 contains at most 50 lines;
 contains at most 81 characters per line, including the ending new line character;
 contains only *s, simple spaces and new line characters.
If the name of the data le is data.txt then your program will be run as a.out <data.txt, so that
you will read the input as if it was coming from the keyboard. What is represented in the data le is
between 1 and 5 pieces of a possibly incomplete tile. The tile is fragmented if the number of pieces
is greater than 1. Four examples of data les are provided: data1.txt, data2.txt, data3.txt
and data4.txt.

Note that what has been represented above is the reconstructed tiles, not what is stored in the
data les, which you should examine while reading this.
Every piece is a polygon whose edges have four possible orientations. You can make the following
assumptions on what is represented in the data le (some assumptions are relevant to only some
of the questions).
 The tile has square corners and is not rotated (it has vertical and horizontal edges).
 The orientation of the pieces w.r.t. the tile is correct: the pieces are neither inverted nor
rotated.
 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.


 Each corner of the tile is intact and preserved.

If a piece can match a corner of the tile, then that piece matches that corner of the tile.

Questions
Q1 Determine whether the tile in the data le is nonfragmented and complete. For this question,
the answer will be either
The tile is intact
or
The tile is not intact
If the tile is intact then no further output will be produced
Q2 Determine the total number of edges of all pieces. For this question, the answer will be of the
form
There is a total of ... edges
Q3 Determine the number of pieces, as well as the number of edges of the piece with the least
number of edges, and the number of edges of the piece with the greatest number of edges.
For this question, the answer will be of the form
There is a unique piece, having ... edges
or
There is a total of ... pieces, that all have ... edges
or
There is a total of ... pieces, that have between ... and ... edges
Q4 Determine whether the tile is complete. For this question, the answer will be either
The tile is complete
or
The tile is incomplete


Sample outputs
$ a.out <data1.txt
The tile is intact
$ a.out <data2.txt
The tile is not intact
There is a total of 7 edges
There is a unique piece, having 7 edges
The tile is incomplete
$ a.out <data3.txt
The tile is not intact
There is a total of 35 edges
There is a total of 4 pieces, that have between 7 and 11 edges
The tile is complete
$ a.out <data4.txt
The tile is not intact
There is a total of 43 edges
There is a total of 4 pieces, that have between 5 and 14 edges
The tile is incomplete
2008-09-12 01:53
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
关于几个条件,要用图形解释,我copy过来就变形状了。。。
我只好解释一下,其实也没太多条件了
几个重要的,一,如果一个图形能够符合矩形的一个角,那么这个图形就肯定是矩形的一个角
就是说,比如你找到一个这样的
*
  *
* * *
三角形,那么这个三角形肯定是矩形的左下角
二,上底或者下底,左边或者右边,必定有一个是只有两块碎片拼成的,也就是说,你能找到四个角,那把它们所在的边分别相加,得到的上底和下底,那个长一些那个就是矩形的底,同样,左边和右边。

三,横排的星间距是2,竖排的是1,斜的是坐标各加1

四,不会出现中间有孔的图形
2008-09-12 02:01
patrick127
Rank: 1
等 级:新手上路
帖 子:10
专家分:0
注 册:2008-9-8
收藏
得分:0 
附件里是sample输入,可以看看,还是有很多需要考虑的地方的
ass2.rar (1.14 KB)
2008-09-12 02:05
葬烟
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2008-9-3
收藏
得分:0 
关于角的问题,不知道我是不是理解错误,按照题目的同行同列距离相等的条件,可以分割出来的角全部都是45度的倍数。
  比如:
       * * * * * * * * * *
                  /        /  \
       * * * * * * * * * *
               /        /        \
       * * * * * * * * * *
            /        /           /
       * * * * * * * * * *
  这个图形,左边一个梯形,中间一个菱形,再边上一个不规则4边形,最边上是两个三角形。它由一个图形分割而成,同行同列星号间距相同,四个原本的直角没有被分割,至少有一条长宽是由两个不规则图形组成(右边的宽,两个三角形),没有旋转,中间没孔。那么,中间那个4边的不规则形本身就有一个直角了。当然这个是旋转过的直角,没旋转过的直角情况是中间有两个背靠背的三角形。统计直角个数的时候不一定只有4个。
   比如说:
       *-*-*-*-*-*-*-*-*-*
        |/ |\ |/ |                 |
       *-*-*-* * * * * * *
        |\ |/                      |
       *-*-*-*-*-*-*-*-*-*
   这个图的话,满足要求,但是直角三角形就有9个。
2008-09-15 22:35
葬烟
Rank: 1
等 级:新手上路
帖 子:40
专家分:0
注 册:2008-9-3
收藏
得分:0 
晕,还有这么一句,Each corner of the tile is intact and preserved.If a piece can match a corner of the tile, then that piece matches that corner of the tile.总共就4个直角了……
2008-09-15 23:35
qGemini
Rank: 1
等 级:禁止访问
帖 子:100
专家分:0
注 册:2008-6-28
收藏
得分:0 
加了这些条件的话,反而更难做了

Gemini  C/C++群57751397
本人不对自己的言论负责

http://
2008-09-16 00:24
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
我只想问一个问题:
*
  *
* * *

到底算不算合格的三角形??因为我的程序只能判断
*
**
* *
这样的三角形,或者:
*
**
* *
*  *
* * *
这样的三角形。

因为横着是空一个格子,但是斜着就是临着在。
我是判断
(-1,-1)(0,-1)(1,-1)
(-2, 0)      (2, 0)
(-1, 1)(0, 1)(1, 1)
这样的坐标的,也就是:
  ***
 * * *
  ***

这样的八个方向。究竟是不是这样的??

我的程序现在可以统计:
    * * * * *  * * * * *  * * * * * * * * * * * *                        
   *        * *         * *                     *
  * *       **           **               * * * *                 
  *         *             *                *
  *                                         *                                   
  *                                          *                  
  *                                           *                        
  *                         *                  *     
  *                        **                   *              
  *                       * *                   *
  *                      *  *                   *                              
  * * * * * * * * * * * *   * * * * * * * * * * *                  


这样的矩形了……不过光是统计就写了80+行………………

[[it] 本帖最后由 StarWing83 于 2008-9-16 03:11 编辑 [/it]]

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-09-16 02:58
StarWing83
Rank: 8Rank: 8
来 自:仙女座大星云
等 级:贵宾
威 望:19
帖 子:3951
专家分:748
注 册:2007-11-16
收藏
得分:0 
= =我发现了我的一个Bug,还没来得及去解决,居然有了解决你的问题的想法。

你知道,你的图形不是凸多边形就是凹多边形。
那么,可以将每个多边形变成三角形,凸的划分,凹的填补。

最后,只需要将这些三角形枚举比较,看看相同角度的边边长是不是相等,就可以决定如何组合了,因为好像所有的数据都不需要旋转……

OK,我继续解决我的Bug……烦恼的凹多边形阿……

专心编程………
飞燕算法初级群:3996098
我的Blog
2008-09-16 03:08
快速回复:发一道题,大家帮忙想想
数据加载中...
 
   



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

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