Triangle fit inside another triangle

Question

Given the lengths of the sides of 2 triangles. Determine if the second triangle can fit inside the first triangle?

For more detailed info read the full problem statement below:

http://acm.timus.ru/problem.aspx?space=1&num=1566&locale=en

My implementation below tries all the (3!)^2 possible combinations of aligning the bases of the triangles. It then tries to shift the second triangle inside the first triangle while checking that the base of the second triangle doesn't exceed the base of the first triangle.

But I keep getting Wrong Answer(WA) #16.

The case I gave is the second image. It is obvious that if you rotate PQR to align the sides of length 2.77 and 3.0 the third vertex will not be inside triangle ABC. The side of length 4.2 can only be aligned along the side of len 5. Thus this case is satisfied only in the configuration show in the second image.

Can you help me find the bug, suggest some test cases where my algorithm breaks down. Alternative algorithms are also welcome.

#include <cmath>
#include <iostream>
using namespace std;

const double PI = atan(1.0)* 4;

// Traingle ABC (Envelope)
double xa, ya, xb, yb, xc, yc;

// Traingle PQR (Postcard)
double xp, yp, xq, yq, xr, yr;

// Angle between sides AB and AC
double theta;

double signWrtLine(double x1, double y1, double x2, double y2, double x, double y)
{
    double A = y2 - y1;
    double B = x1 - x2;
    double C = -(A * x1 + B * y1);

    return (A * x + B * y + C);
}

bool fit()
{ 
    if ((xr > xc) || (yq > yb)) return false;

    if (signWrtLine(xa, ya, xb, yb, xq, yq) < 0) {
        double d = (yq / tan(theta)) - xq;
        return (xr + d <= xc);
    }

    return (signWrtLine(xa, ya, xb, yb, xq, yq) >= 0 && 
            signWrtLine(xb, yb, xc, yc, xq, yq) >= 0 && 
            signWrtLine(xc, yc, xa, ya, xq, yq) >= 0);
}

bool fit(double a[], double b[])
{
    // generate the 3! permutations of the envelope
    // loops i,k
    for (int i = 0; i < 3; i++) {

        double angle;
        double u = a[i], v = a[(i + 1) % 3], w = a[(i + 2) % 3];

        for (int k = 0; k < 2; k++) {
            switch (k) {
            case 0:
                xa = 0, ya = 0;
                angle = theta = acos((u * u + v * v - w * w) / (2 * u * v));
                xb = v * cos(angle), yb = v * sin(angle);
                xc = u, yc = 0;     
                break;
            case 1:
                // reflect envelope
                swap(v, w);
                angle = theta = acos((u * u + v * v - w * w) / (2 * u * v));
                xb = v * cos(angle), yb = v * sin(angle);       
                break;
            }

            // generate the 3! permutations of the postcard
            // loops j,k
            for (int j = 0; j < 3; j++) {

                double angle;
                double u = b[j], v = b[(j + 1) % 3], w = b[(j + 2) % 3];

                for (int k = 0; k < 2; k++) {
                    switch (k) {
                    case 0:
                        xp = 0, yp = 0;
                        angle = acos((u * u + v * v - w * w) / (2 * u * v));
                        xq = v * cos(angle), yq = v * sin(angle);
                        xr = u, yr = 0;
                        break;
                    case 1:
                        // reflect postcard
                        swap(v, w);
                        angle = acos((u * u + v * v - w * w) / (2 * u * v));
                        xq = v * cos(angle), yq = v * sin(angle);
                        break;
                    }

                    if (fit()) return true;
                }
            }
        }
    }
    return false;
}


int main()
{
    double a[3], b[3];

    for (int i = 0; i < 3; i++) cin >> a[i];
    for (int i = 0; i < 3; i++) cin >> b[i];

    if(fit(a, b)) cout << "YES" << endl;
    else cout << "NO" << endl;

    return 0;
}

Answer 1

Barycentric coordinates! In detail:

Let the "envelope" triangle have vertices A, B, C; without loss of generality you can place vertex A at the origin and align the side AB with the +x axis. Use the edge lengths of the envelope triangle to find the angle at vertex A, i.e., the angle between the sides AB and AC. Using this angle, you define a new coordinate system (u,v); in this coordinate system the vertex coordinates are A=(0,0), B=(1,0) and C=(0,1).

Now, take the other triangle with vertices A',B',C', and find first the XY coordinates of the 3 vertices for each case of: (A'B', B'C', A'C') aligned with +x coordinate axis. For each such alignment, transform the other two vertices to the UV-coordinate system determined by the envelope triangle. If it happens that both of the other vertices have (u,v) coordinates with 0 <= u,v <= 1 with u+v<=1, the triangle fits within the envelope triangle.

Angle between two sides can be obtained through the sine theorem for planar triangles; though you have to be a bit careful if the angle at a vertex is obtuse (> PI/2) since the sine function is symmetric around PI/2 on the interval [0,PI]. To check whether the angle is obtuse, you also need to use the cosine theorem, though you don't need to calculate the cosine itself: if |AB|^2 + |AC|^2 > |BC|^2, the angle at A is obtuse.

I think that about sums it up.

Answer 2

//23/08/11 13:56
//determine if a triangle will fit inside a second triangle
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
const double pi= 3.1414926;
const double tri=180;//deg in triangle
double find_B_ang(double a,double b,double c);
double find_C_ang(double a,double b,double c);
double movetri_r , tc_ghosthor_B;
int main()
{double a=0.0,b=0.0,c=0.0,x=0.0,y=0.0,z=0.0;
double A=0.0,B=0.0,C=0.0,A1=0.0,B1=0.0,C1=0.0;// L&R base angles
double te_vert_B=0.0,te_hor_B=0.0,te_hor_C=0.0;
double tc_vert_B=0.0,tc_hor_B=0.0,tc_hor_C=0.0;
//points B and B1 are considered co-incedent
cout<<"\n\ndetermine if a triangular card will fit inside\n"
    <<"a triangular envelope\n";
//envelope dimensions    
cout<<"\nenter lengths of the sides of envelope (space between)\n";
cout<<"ensure longest of them is less than sum of other two\n";
do
{
   cin>>a>>b>>c;//the e sides
   if(c>a)swap(a,c);//sort sides in decending order
   if(b>a)swap(a,b);
   if(c>b)swap(b,c);
   if(a >(b+c))
   cout<<"WRONG...b+c must be greater than a";
}while(a >(b+c));


cout<<"\nthe sides of the envelope are "<<a<<','<<b<<','<<c<<endl;
B=find_B_ang(a,b,c);
C=find_C_ang(a,b,c);
te_vert_B=c*sin(B*pi/tri);//apex to base vertical line
te_hor_B=te_vert_B/tan(B*pi/tri);//B to vertical line
te_hor_C=a-te_hor_B;//C to vertical line

cout<<"-------------------------------------------\n";
//card dimensions
do
{
cout<<"\nenter lengths of sides of card (space between) \n"; 
cout<<"ensure longest of them is less than sum of other two\n";
do
{
   cin>>x>>y>>z;//the c sides
   if(z>x)swap(z,x);//sort sides in decending order
   if(y>x)swap(y,x);
   if(z>y)swap(y,z);
   if(x>(y+z))
   cout<<"WRONG...y+z must be greater than x\n";
}while(x>(y+z));

cout<<"\nthe sides of card are "<<x<<','<<y<<','<<z<<endl;//x is base
B1=find_B_ang(x,y,z);
C1=find_C_ang(x,y,z);
tc_vert_B=z*sin(B1*pi/tri);//apex to base vertical line
tc_hor_B=tc_vert_B/tan(B1*pi/tri);//B to vertical line
tc_hor_C=x-tc_hor_B;//C to vertical line
tc_ghosthor_B=tc_vert_B/tan(B*pi/tri);
movetri_r= abs(tc_ghosthor_B-tc_hor_B);    
cout<<"------------------------------------------------\n";
//determine and advise if card fits within envelope    
if(B1<B && tc_vert_B <(tc_hor_C + a-x)*tan(C*pi/tri))cout<<"\ntrue";
else if(B1<B && tc_hor_B< te_hor_B && tc_vert_B<te_vert_B)cout<<"true";
else if(B1>B && movetri_r<a-x && tc_vert_B<te_vert_B)cout<<"true";
else cout<<"\nfalse";
} while(x>0);
cout<<"\npress any key...";
cin.ignore();
cin.get();
return 0;
}
double find_B_ang(double a,double b,double c)
{
 double X=0.0;
 X=((a*a)+(c*c)-(b*b));
 X/=2*a*c;
 X=acos(X);
 X*=tri/pi;
 return X; //degrees
}
double find_C_ang(double a,double b,double c)
{
 double X=0.0;
 X=((a*a)+(b*b)-(c*c));
 X/=2*a*b;       
 X=acos(X);
 X*=tri/pi;
 return X;//degrees
}