c++ - 三角形适合另一个三角形

Question

给定 2 个三角形的边长。确定第二个三角形是否可以放入第一个三角形内？

有关更多详细信息，请阅读下面的完整问题陈述:

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

我下面的实现尝试了对齐三角形底边的所有 (3!)^2 种可能组合。然后它尝试将第二个三角形移动到第一个三角形内，同时检查第二个三角形的底边不超过第一个三角形的底边。

但我一直收到错误答案 (WA) #16。

我给的案例是第二张图。很明显，如果您旋转 PQR 以对齐长度为 2.77 和 3.0 的边，则第三个顶点将不会在三角形 ABC 内。长度为 4.2 的边只能沿着 len 5 的边对齐。因此这种情况仅在第二张图中显示的配置中得到满足。

你能帮我找到错误吗，建议一些我的算法崩溃的测试用例。也欢迎使用替代算法。

#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

重心坐标!详细说明:

让“信封”三角形有顶点A、B、C；在不失一般性的情况下，您可以将顶点 A 放在原点并将边 AB 与 +x 轴对齐。使用包络三角形的边长求顶点 A 处的角度，即边 AB 和 AC 之间的角度。使用这个角度，您定义了一个新的坐标系 (u,v)；在此坐标系中，顶点坐标为 A=(0,0)、B=(1,0) 和 C=(0,1)。

现在，取另一个顶点为 A'、B'、C' 的三角形，并首先找到以下每种情况下 3 个顶点的 XY 坐标:(A'B', B'C', A'C' ) 与 +x 坐标轴对齐。对于每个这样的对齐方式，将其他两个顶点转换为由包络三角形确定的 UV 坐标系。如果碰巧其他两个顶点都具有 (u,v) 坐标且 0 <= u,v <= 1 且 u+v<=1，则三角形适合包络三角形。

平面三角形的两条边之间的夹角可以通过正弦定理得到；尽管如果顶点处的角度是钝角 (> PI/2)，则必须小心一点，因为正弦函数在区间 [0,PI] 上围绕 PI/2 对称。要检查角度是否为钝角，您还需要使用余弦定理，尽管您不需要计算余弦本身:如果 |AB|^2 + |AC|^2 > |BC|^2，则角度A 是钝角。

我想总结一下。