有一段时间没有做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
|
32 |
0.170 |
792 |
C |
2002-02-04 07:02:47 |
732386 |
|
|
33 |
0.172 |
1160 |
C++ |
2007-05-02 16:05:54 |
5551868 |
|
|
34 |
0.174 |
404 |
C |
2001-08-30 08:46:54 |
539862 |
// // ACM UVa Problem #209// http://acm.uva.es/p/v2/209.html//// Author: ATField// Email: atfield_zhang@hotmail.com//#include stdio.h>#include stdlib.h>#include string.h>#define MAX 65535struct point
...{
public : bool is_coincide(const point &pt) const
...{ // not allow testing points with same coordinates if( _x == pt._x && _y == pt._y ) return false; if( _y == pt._y ) return true; else ...{ int k1 = abs( _x - pt._x ); int k2 = abs( _y - pt._y ); if( k1 == k2 ) return true;
} return false; } int get_dist(const point &pt) const ...{ // not allow testing points with same coordinates if( _x == pt._x && _y == pt._y ) return 0; if( _y == pt._y ) return abs(_x - pt._x) >> 1; // need to divide by 2 else ...{ int k1 = abs( _x - pt._x ); int k2 = abs( _y - pt._y ); if( k1 == k2 ) return k1; } return 0; }public : static const int X_DELTA = 2; static const int Y_DELTA = 3; static const int LEN = 4;public : int _x; int _y; int _valid;private : static point s_all_points[MAX];public : static void prepare() ...{ int level = 0; int before_next_level = 1; int next_x = 0; int next_y = 0; for( int i = 1; i MAX ; ++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; } } static point *all_points() ...{ return s_all_points; }
};