Приведены длины сторон 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;
}