Problem C
Triangle Partitioning
Input: standard input
Output: standard output
Time Limit: 1 second
 

A triangle can be divided into two equal triangle by drawing a median on its largest edge (In the figure below, or above such a division is shown with the red line). Then the smaller two triangles can be divided in similar fashion into equal triangles (Shown in the picture below with blue lines). This process can continue forever.

Some mathematicians have found that we have only some "styles" of triangles they only differs in sizes when we split triangle into small ones in the method specified above. So now given the length of the sides of the triangle your job is to find out how many different styles of small triangles do we have. Two triangles are of same style when they are similar triangles.

Input

First line of the input file contains an integer N (0<N<35) that indicates how many lines of inputs are there.

Each line contains three integers a, b, c (0<a,b,c<100) which indicates the sides of a valid triangle. A valid triangle means a real triangle with positive area.

Output

For each line of input you should produce one line of output, which contains the serial of output followed by an integer T, which indicates the number of different styles of small triangles, formed for that particular triangle. Look at the output for sample input for details. You can safely assume that for any triangle T will be less than 100.

Sample Input                                 Output for Sample Input

Idea supplied by Thanh Vy, Composed for Uva OJ by Shahriar Manzoor, EPS

Special Thanks: Derek Kisman, EPS

題目描述：

給一個三角形的三邊，每次將最大邊上做一條中線，此時會畫分成兩個新的三角形，

新的三角形也繼續畫分下去。請問這個做法途中最多產生多少不同的相似形？

題目解法：

模擬計算中線長，並且使用 BFS 拓展可能的相似形。

必須使用去重複的判斷。

#include <stdio.h>
#include <set>
#include <algorithm>
#include <math.h>
#include <queue>
using namespace std;
struct triangle {
    double a, b, c;//a > b > c
    triangle(double p, double q, double r) {
        a = p, b = q, c = r;
        if(b > a) swap(a, b);
        if(c > a) swap(a, c);
        if(c > b) swap(b, c);
        b /= a, c /= a;
        a = 1;
    }
    #define eps 1e-8
    bool operator<(const triangle &x) const {
        if(fabs(a-x.a) > eps)    return a < x.a;
        if(fabs(b-x.b) > eps)    return b < x.b;
        if(fabs(c-x.c) > eps)    return c < x.c;
        return false;
    }
};
int main() {
    int testcase, cases = 0;
    double a, b, c;
    scanf("%d", &testcase);
    while(testcase--) {
        scanf("%lf %lf %lf", &a, &b, &c);
        set<triangle> S;
        queue<triangle> Q;
        Q.push(triangle(a, b, c)), S.insert(triangle(a, b, c));
        while(!Q.empty()) {
            triangle t = Q.front();
            Q.pop();
            a = t.a, b = t.b, c = t.c;
            double cosB = (a*a+c*c-b*b)/(2*a*c);
            double mid = sqrt(c*c+a*a/4-2*c*(a/2)*cosB);
            if(S.find(triangle(c, mid, a/2)) == S.end()) {
                Q.push(triangle(c, mid, a/2));
                S.insert(triangle(c, mid, a/2));
            }
            if(S.find(triangle(b, mid, a/2)) == S.end()) {
                Q.push(triangle(b, mid, a/2));
                S.insert(triangle(b, mid, a/2));
            }
        }
        printf("Triangle %d: %d\n", ++cases, S.size());
    }
    return 0;
}