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

Use epsilon (1e-10) when comparing doubles!