ACM UVa算法题209 Triangular Vertices的解法

happmaoo

浏览: 4430370 次
性别:
来自: 杭州

最近访客更多访客>>

fgken

flyjava

icesort

adamkisy

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

2013-06 ( 10)
2012-01 ( 29)
2011-12 ( 23)
更多存档...

算法 F#J#EXT

有一段时间没有做ACM算法题目了，今天正好有空便随便挑了209题来做做：ACM UVa算法题#209题

这道题有几个要点：

1. 给定坐标系

坐标系很容易定，我采用的是第一个点为(0, 0)点，X方向差别为2个单位，Y方向差别为1个单位，点之间的距离，也就是LEN为1个单位，这样便于计算。注意我用的不是实际长度，而是抽象的单位，这个单位在不同方向上面意义不一样，否则很容易通过三角形相关公理推出这样的三角形不存在，我们关心的只是这样的一个对应关系。这里的人为设定确实有些Confusing，我之前也是按照一般的三角形的长度，如3，4，5来定义，但是后来发现这样做做的乘除法太多，过于浪费CPU Cycle，如果按照我这样的设定，大部分情况只用到加减法，另外一种情况只需用到移位操作即可。

参看下图：

2. 判断是否两点连线是一条边(Coincide)

这里可以分两种情况：

a. Y1 = y2, 必然是Coincide

b. 否则，X_Delta = abs(x1 – x2), Y_Delta = abs(y1 – y2)，由于之前我们人为设定X方向差别为2个单位，Y方向差别为1一个单位，因此只要X_Delta = Y_Delta即可

3. 计算距离

假定是Coincide的情况，否则直接返回出错，因为在非Coincide的情况无需计算距离。此外，由于这里已经知道是Coincide，并且我们并没有统一单位，所以这里不能也不应该用勾股定理来计算长度，而是采用比例的方法，同样分两种情况，参考上图：

a. Y1 = y2, 那么因为X方向上两个单位对应一个长度Unit，所以长度=abs(x1 – x2) >> 1;

b. 否则，长度Unit的个数和X/Y方向（任意）的差别相等，也就是长度=abs(x1 – x2)

4. 判断是否是目标图形，并且每条边相等

对于三角形，很简单，直接对3条边判断即可，没有什么变数。对于四边形和六边形就不同了，需要用到遍历来确定一个从某点开始（我们可以固定为第一个点）遍历所有点最后回到该点的环，并且每条边长度均相等，注意这里由于题目的特殊性，不用判断平行等条件。可以用一个邻接矩阵来代表对应的边的长度，这个应该一次性计算出来，如果非Coincide则设置为某个特殊值，比如0

刚开始提交的时候，Rank是45，之后我又做了下面的优化：

1. 当遍历尝试完毕从最初点出发的某条边的时候，说明这一边不可能成为环，将其置为0表示不可通，并且遍历从最初点出发的其他同样长度的边，置为0，减少遍历次数

2. 在初始化计算所有点的坐标的时候改变了一点点算法，用加减法代替乘法

3. 最初坐标采用的是实际的长度，而不是像上面那样用不同的抽象单位算出，修改之后减少了大量乘除法计算

4. 调整遍历算法，由于从初始点出发之后，后3个点必然不能是初始点，因此做了一点修改对这个情况作了优化

5. 修改对邻接矩阵的算法，由于adj[i][j] = adj[j][i]，所以只需计算矩阵的一半即可

修改之后再提交Rank变成了33，似乎是目前个人的最好纪录 J

0.170

792

LittleJohn Yo

2002-02-04 07:02:47

732386

0.172

1160

Yi Zhang

C++

2007-05-02 16:05:54

5551868

0.174

404

Rodrigo Malta Schmidt

2001-08-30 08:46:54

539862

代码如下：

//ACMUVaProblem#209

//http://acm.uva.es/p/v2/209.html

//Author:ATField

//Email:atfield_zhang@hotmail.com

#includestdio.h>

#includestdlib.h>

#includestring.h>

#defineMAX65535

structpoint

{

public:

boolis_coincide(constpoint&pt)const

{

//notallowtestingpointswithsamecoordinates

if(_x==pt._x&&_y==pt._y)

returnfalse;

if(_y==pt._y)

returntrue;

else

{

intk1=abs(_x-pt._x);

intk2=abs(_y-pt._y);

if(k1==k2)

returntrue;

}

returnfalse;

}

intget_dist(constpoint&pt)const

{

//notallowtestingpointswithsamecoordinates

if(_x==pt._x&&_y==pt._y)

return0;

if(_y==pt._y)

returnabs(_x-pt._x)>>1;//needtodivideby2

else

{

intk1=abs(_x-pt._x);

intk2=abs(_y-pt._y);

if(k1==k2)

returnk1;

}

return0;

}

public:

staticconstintX_DELTA=2;

staticconstintY_DELTA=3;

staticconstintLEN=4;

public:

int_x;

int_y;

int_valid;

private:

staticpoints_all_points[MAX];

public:

staticvoidprepare()

{

intlevel=0;

intbefore_next_level=1;

intnext_x=0;

intnext_y=0;

for(inti=1;iMAX;++i)

{

s_all_points[i]._x=next_x;

s_all_points[i]._y=next_y;

before_next_level--;

if(before_next_level==0)

{

level++;

before_next_level=level+1;

next_x=-level;

next_y++;

}

else

next_x+=2;

}

staticpoint*all_points()

{

returns_all_points;

}

};

pointpoint::s_all_points[MAX];

boolcheck_triangle(int*n)

{

//1.Duplicates

//Noneedtocheckduplicatebecausethefollowingcheckswilldo

//2.Coincide

//Checkeveryedge

point*points=point::all_points();

if(points[n[0]].is_coincide(points[n[1]])&&

points[n[0]].is_coincide(points[n[2]])&&

points[n[1]].is_coincide(points[n[2]]))

{

//3.Samelength

//Checkeveryedge

intlen=points[n[0]].get_dist(points[n[1]]);

if(len==points[n[0]].get_dist(points[n[2]])&&

len==points[n[1]].get_dist(points[n[2]]))

returntrue;

}

returnfalse;

}

boolinit_adj(int*n,intnum,intadj[6][6])

{

point*points=point::all_points();

for(inti=0;inum;++i)

{

for(intj=i;jnum;++j)

{

if(i==j)

{

adj[i][j]=0;

adj[j][i]=0;

}

else

{

//1.Duplicates

//Returnfalsewhenfoundduplicate

if(n[i]==n[j])

returnfalse;

//2.Coincide&Len(Whennotcoincide,len=0)

adj[i][j]=points[n[i]].get_dist(points[n[j]]);

adj[j][i]=adj[i][j];

}

returntrue;

}

intfind_same_len_loop(intadj[6][6],intnum)

分享到：

另一道看上去很吓人的面试题：如何交换a和 ... | 手动生成C#的COM包装类的常见问题和解决办 ...

2007-12-18 23:25
浏览 603
评论(0)
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论