Треугольник вписывается в другой треугольник
Даны длины сторон 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;
}
4 ответа
Барицентрические координаты! В деталях:
Пусть "огибающий" треугольник имеет вершины A, B, C; без ограничения общности вы можете поместить вершину A в начало координат и выровнять сторону AB с осью +x. Используйте длины ребер огибающего треугольника, чтобы найти угол в вершине A, т. Е. Угол между сторонами AB и AC. Используя этот угол, вы определяете новую систему координат (u,v); в этой системе координат координатами вершины являются A=(0,0), B=(1,0) и C=(0,1).
Теперь возьмите другой треугольник с вершинами A',B',C'и найдите сначала координаты XY 3 вершин для каждого случая: (A'B', B'C', A'C'), выровненного по + х координатная ось. Для каждого такого выравнивания преобразуйте две другие вершины в систему координат UV, определяемую треугольником огибающей. Если случится, что обе другие вершины имеют координаты (u, v) с 0 <= u,v <= 1 с u+v<=1, треугольник вписывается в треугольник огибающей.
Угол между двумя сторонами может быть получен через теорему синуса для плоских треугольников; хотя вы должны быть немного осторожны, если угол в вершине тупой (> PI/2), так как функция синуса симметрична относительно PI / 2 на интервале [0,PI]. Чтобы проверить, является ли угол тупым, вам также нужно использовать теорему косинуса, хотя вам не нужно вычислять сам косинус: если |AB|^2 + |AC|^2 > |BC|^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
}
Можете попробовать отсюда - http://www.springerlink.com/content/t10266u5832477w7/. Кажется, что проблема до сих пор не решена, поэтому лучше всего пойти на некоторые эвристики, чтобы получить простые случаи (например, проверки на вписанные / описанные круги, выравнивание границ и т. Д.) И надеяться на лучшее.