学步园

struct Triangle<br /> {<br /> Triangle(int _a = 0, int _b = 0, int _c = 0) { a = _a; b = _b; c = _c; }<br /> int a, b, c;<br /> };</p> <p>inline void Swap(int &lhs, int &rhs)<br /> {<br /> int temp;<br /> temp = lhs; lhs = rhs; rhs = temp;<br /> }</p> <p>//<br /> // 将三角形的边长从小到大排序<br /> //////////////////////////////////////////////////////////////////////////<br /> void SortEdge(Triangle &tri)<br /> {<br /> if (tri.a > tri.b) { Swap(tri.a, tri.b); }<br /> if (tri.b > tri.c) { Swap(tri.b, tri.c); }<br /> if (tri.a > tri.b) { Swap(tri.a, tri.b); }<br /> }</p> <p>//<br /> // 判断两个三角形是否相似<br /> //////////////////////////////////////////////////////////////////////////<br /> bool IsSimilar(const Triangle &tri1, const Triangle &tri2)<br /> {<br /> int larger, smaller;<br /> larger = tri1.a; smaller = tri2.a;<br /> if (larger < smaller) Swap(larger, smaller);<br /> if (larger % smaller != 0) return false;<br /> larger = tri1.b; smaller = tri2.b;<br /> if (larger < smaller) Swap(larger, smaller);<br /> if (larger % smaller != 0) return false;<br /> larger = tri1.c; smaller = tri2.c;<br /> if (larger < smaller) Swap(larger, smaller);<br /> if (larger % smaller != 0) return false;<br /> return true;<br /> }</p> <p>//<br /> // 统计相似三角形的数目<br /> //////////////////////////////////////////////////////////////////////////<br /> int SimilarCount(Triangle* triArr, int size)<br /> {<br /> int count = 0;<br /> int *flagArr = new int[size];<br /> memset(flagArr, 0, sizeof(int) * size);<br /> for (int i = 0; i < size; i++)<br /> {<br /> for (int j = i + 1; j < size; j++)<br /> {<br /> SortEdge(triArr[i]);<br /> SortEdge(triArr[j]);<br /> if (IsSimilar(triArr[i], triArr[j]) && flagArr[i] ==0 && flagArr[j] == 0)<br /> {<br /> count++;<br /> flagArr[i] = flagArr[j] = 1;<br /> }<br /> }<br /> }<br /> delete []flagArr;<br /> return count;<br /> }</p> <p>int main(int argc, char* argv[])<br /> {<br /> Triangle triArray[10] =<br /> {<br /> Triangle(2, 2, 3),<br /> Triangle(4, 4, 6),<br /> Triangle(9, 6, 6),<br /> Triangle(3, 4, 2),<br /> Triangle(3, 4, 2),<br /> Triangle(2, 5, 6),<br /> Triangle(4, 10, 12),<br /> Triangle(1, 1, 1),<br /> Triangle(2, 2, 2),<br /> Triangle(3, 3, 3)<br /> };<br /> cout << SimilarCount(triArray, 10);<br /> return 0;<br /> }<br />