Contest - 2013校賽暨華中邀請賽 Problem D: Tetrahedron Inequality

Problem D: Tetrahedron Inequality
Time Limit: 1 Sec Memory Limit: 128 MB
Submit: 14 Solved: 2
[Submit][Status][Web Board]
Description
It is well known that you cannot make a triangle with non-zero area whose sides have lengths 1, 2, 3. Can you make a tetrahedron(四面體) with non-zero volume whose edges have lengths 1, 2, 3, 4, 5, 6?

Input
The first line of input contains an integer 0 < n <= 10000, the number of lines to follow. Each of the next n lines contains six positive integers separated by spaces, the lengths of the edges of the desired tetrahedron. The length of each edge is no greater than 1000000.

Output
Output n lines, each containing the word YES if it is possible to construct a tetrahedron with non-zero volume with the given edge lengths, or the word NO if it is not possible.

Sample Input
2
1 2 3 4 5 6
10 10 10 10 10 18
Sample Output
NO
NO題意：輸入六個數讓你判斷他們能否組成四面體。上次去抵達比賽沒做出來的，當時想的太簡單了，一直WA，比賽結束後才知道為什麼，是任選五條邊的各種三角形的組合沒考慮。今天又做了一下，很快寫好了，可是想AC還是不容易啊，具體的看注釋吧

/**************************************************************
Problem: 1432
User: wust_*******
Language: C
Result: Accepted
Time:44 ms
Memory:760 kb

#include<stdio.h>    
#include<math.h>    
    
int judge(double a,double b,double c)   
{   
    if(a+b>c&&a+c>b&&b+c>a) //能否組成三角形   
        return 1;   
    else return 0;   
}   
    
int cal(double a,double b,double c,double d,double e,double f)   
{   
    if(a>1000) //因為題目說明了邊的范圍<=1000000<SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif; FONT-SIZE: 12px">，</SPAN><SPAN style="FONT-SIZE: 18px"><SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">如果輸入1000000的邊長</SPAN><SPAN style="FONT-FAMILY: Arial, Helvetica, sans-serif">,看看後面的帶乘法的運算每一個都能爆掉，這就是剛才WA好多的原因，所以對大數據要同時除以1000.0</SPAN></SPAN> 

  {   
        a/=1000.0;   
        b/=1000.0;   
        c/=1000.0;   
        d/=1000.0;   
        e/=1000.0;   
        f/=1000.0;   
    }   
    double L1,L2,h1,h2,x1,x2,ff;   
    L1=(a+b+d)/2.0;   
    L2=(a+c+e)/2.0;   
    h1=2*sqrt(L1)*sqrt(L1-a)/a*sqrt(L1-b)*sqrt(L1-d);// 算高的   
    h2=2*sqrt(L2)*sqrt(L2-a)/a*sqrt(L2-c)*sqrt(L2-e);   
    x1=(b*b+e*e-d*d-c*c)/4/a/a*(b*b+e*e-d*d-c*c);//兩個三角形高之間的距離平方   
    ff=f*f;   
    if(ff<(h1+h2)*(h1+h2)+x1&&ff>(h1-h2)*(h1-h2)+x1) //根據任意可以組成兩個三角形的五條邊來算第六條邊f的長度范圍，看f是否在這個范圍內   
        return 1;   
    else return 0;   
}   
int main()   
{   
    int t,a,b,c,d,e,f,i,j;   
    double r[6];   
    scanf("%d",&t);   
    while(t--)   
    {   
        for(i=0;i<6;i++)   
            scanf("%lf",&r[i]);   
        for(j=0,a=0;a<5;a++)   
        {   
            for(b=0;b<5;b++)   
            {   
                if(a!=b)   
                for(c=0;c<5;c++)   
                {   
                    if(a!=c&&b!=c) //保證不會選重邊   
                    for(d=0;d<5;d++)   
                    {   
                        if(a!=d&&d!=c&&b!=d&&judge(r[a],r[b],r[d]))   
                        for(e=0;e<5;e++)   
                        {   
                            if(a!=e&&d!=e&&b!=e&&c!=e)   
                            if(judge(r[a],r[c],r[e]))   
                            {   
                                if(cal(r[a],r[b],r[c],r[d],r[e],r[5])) //計算能否組成四面體   
                                {   
                                    j++;   
                                    break; //有一個成立就退出循環   
                                }   
                            }   
                            if(j)   
                                break;   
                        }   
                        if(j)   
                            break;   
                    }   
                    if(j)   
                        break;   
                }   
                if(j)   
                    break;   
            }   
            if(j)   
                break;   
        }   
        if(j)   
            printf("YES\n");   
        else printf("NO\n");   
    }   
    return 0;   
}   

    { 
        a/=1000.0; 
        b/=1000.0; 
        c/=1000.0; 
        d/=1000.0; 
        e/=1000.0; 
        f/=1000.0; 
    } 
    double L1,L2,h1,h2,x1,x2,ff; 
    L1=(a+b+d)/2.0; 
    L2=(a+c+e)/2.0; 
    h1=2*sqrt(L1)*sqrt(L1-a)/a*sqrt(L1-b)*sqrt(L1-d);// 算高的
    h2=2*sqrt(L2)*sqrt(L2-a)/a*sqrt(L2-c)*sqrt(L2-e); 
    x1=(b*b+e*e-d*d-c*c)/4/a/a*(b*b+e*e-d*d-c*c);//兩個三角形高之間的距離平方
    ff=f*f; 
    if(ff<(h1+h2)*(h1+h2)+x1&&ff>(h1-h2)*(h1-h2)+x1) //根據任意可以組成兩個三角形的五條邊來算第六條邊f的長度范圍，看f是否在這個范圍內
        return 1; 
    else return 0; 
} 
int main() 
{ 
    int t,a,b,c,d,e,f,i,j; 
    double r[6]; 
    scanf("%d",&t); 
    while(t--) 
    { 
        for(i=0;i<6;i++) 
            scanf("%lf",&r[i]); 
        for(j=0,a=0;a<5;a++) 
        { 
            for(b=0;b<5;b++) 
            { 
                if(a!=b) 
                for(c=0;c<5;c++) 
                { 
                    if(a!=c&&b!=c) //保證不會選重邊
                    for(d=0;d<5;d++) 
                    { 
                        if(a!=d&&d!=c&&b!=d&&judge(r[a],r[b],r[d])) 
                        for(e=0;e<5;e++) 
                        { 
                            if(a!=e&&d!=e&&b!=e&&c!=e) 
                            if(judge(r[a],r[c],r[e])) 
                            { 
                                if(cal(r[a],r[b],r[c],r[d],r[e],r[5])) //計算能否組成四面體
                                { 
                                    j++; 
                                    break; //有一個成立就退出循環
                                } 
                            } 
                            if(j) 
                                break; 
                        } 
                        if(j) 
                            break; 
                    } 
                    if(j) 
                        break; 
                } 
                if(j) 
                    break; 
            } 
            if(j) 
                break; 
        } 
        if(j) 
            printf("YES\n"); 
        else printf("NO\n"); 
    } 
    return 0; 
}