Треугольник помещается в другой треугольник ⇐ C++

[Anonymous]

Учитывая длину сторон 2 треугольников. Определите, может ли второй треугольник вписаться внутри первого треугольника? http://acm.timus.ru/problem.aspx?space= ... &locale=en

Моя реализация ниже пытается все (3!)^ 2 Возможные комбинации выравнивания оснований треугольников. Затем он пытается сместить второй треугольник внутри первого треугольника, проверяя, что основание второго треугольника не превышает основание первого треугольника. < /P>

Но я держу Получение неправильного ответа (WA) #16.



Дело, которое я дал, является вторым изображением. Очевидно, что если вы поверните PQR, чтобы выровнять стороны длины 2,77 и 3.0, третья вершина не будет внутри треугольника ABC. Сторона длины 4.2 может быть выровнен только вдоль стороны Лена 5. Таким образом Найдите ошибку, предложите некоторые тестовые случаи, когда мой алгоритм разрушается. Альтернативные алгоритмы также приветствуются. < /P>

#include
#include
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 = 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, 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;
for (int i = 0; i < 3; i++) cin >> b;

if(fit(a, b)) cout

Подробнее здесь: https://stackoverflow.com/questions/705 ... r-triangle