×

# TUZTRN - Editorial

Author: Pavel Sheftelevich
Tester: Kanstantsin Sokal
Editorialist: Sunny Aggarwal

Medium

# Pre-Requisite:

Geometry, Implementation, Mathematics

# Problem Statement:

Given 2 triangles and a quadrilateral. We are asked to check whether it's possible to combine these triangles by moving, flipping and/or rotating them, and cover exactly the quadrilateral with no overlap between the two triangles.

# Brief Explanation:

There are no so many possible configurations in which we can combine given 2 triangles to form a quadrilateral such that there is no overlap between the triangles.

• 1 side of a triangle is put against equal length side of other triangle to form quadrilateral.

• 1 side of a triangle is put against relatively longer side of other triangle to form quadrilateral.

Check all above listed configurations.

# Solution:

$1^{st} Configuration$

One side of the first triangle is put against the same-length side of the second triangle. This case can also degenerate into a case, when quadrangle appears to be a triangle. Any way, we should fix which sides will be put against each other and them try all possible combinations of the remaining sides to complete the quadrangle.

$2^{nd} Configuration$

One side of one triangle is put against a longer side of the other triangle in such a way, that it continues one of the sides of the second triangle (like on the picture attached to this letter). In this case, we should fix the part of the side of the second triangle, which is next to the one put against the shorter side of the first triangle, and then intersect the line formed by the part of the side and the opposite side of the quadrangle.

How to check for these configurations ?

Some Pre-Requisites

Please have a look at given code. I have tried to cover the implementation in the comments.

C++ Code

#define X first
#define Y second
#define pb push_back
#define ld long double
const ld eps = 1E-6, PI = acos(-1.0);
vector<ld>l1, l2;
pair<ld, ld>p[4];

ld dist(pair<ld, ld> A, pair<ld, ld>B) {
// finding euclidean between 2 coordinates
return sqrt( (A.X - B.X) * (A.X - B.X) + (A.Y - B.Y) * (A.Y - B.Y) );
}

ld area(pair<ld, ld>A, pair<ld, ld>B, pair<ld, ld>C) {
// finding 2 * area of triangle formed by these 3 coordinates.
return A.X * (B.Y - C.Y) + B.X * (C.Y - A.Y) + C.X * (A.Y - B.Y) ;
}

int n, m;
ld given[10][10];
ld g[10][10];

bool eq(ld a, ld b) {
return fabs(a - b) < eps;
}

ld angle(ld a, ld b, ld c) {
return acos ( (a*a + b*b  - c*c) / (2.0 * a * b) );
}

ld side(ld a, ld b, ld ang) {
return sqrt( a*a + b*b  - 2 * cos(ang)*a*b );
}

void assign(int a, int b, ld c) {
g[a][b] = g[b][a] = c;
}

bool check() {
if (n != m)
return false;
vector<int>perm;
for (int i = 0; i < m; i++)
perm.pb(i);
for (int i = 0; i < n; i++) {
perm.pb(perm[0]);
perm.erase(perm.begin() );
bool ok = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ( !eq( g[ perm[i] ][ perm[j] ], given[i][j]) ) {
ok = false;
}
}
}
if (ok) {
return true;
}
}
perm.clear();

for (int i = m - 1; i >= 0; i--)
perm.pb(i);

for (int i = 0; i < n; i++) {
perm.pb(perm[0]);
perm.erase(perm.begin() );
bool ok = true;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if ( !eq( g[ perm[i] ][ perm[j] ], given[i][j]) ) {
ok = false;
}
}
}
if (ok) {
return true;
}
}
return false;
}

void solve() {
pair<ld, ld>a, b, c;
cin>>a.X>>a.Y;
cin>>b.X>>b.Y;
cin>>c.X>>c.Y;

l1.clear(); l2.clear();

l1.pb( dist(a, b) ); l1.pb ( dist(a, c) ); l1.pb( dist(b, c) );
// l1 contains length of sides of first triangle

cin>>a.X>>a.Y;
cin>>b.X>>b.Y;
cin>>c.X>>c.Y;

l2.pb( dist(a, b) ); l2.pb ( dist(a, c) ); l2.pb( dist(b, c) );
// l2 contains lengths of sides of second triangle

sort(l1.begin(), l1.end() );
sort(l2.begin(), l2.end() );

for (int i = 0; i < 4; i++) {
cin>>p[i].X>>p[i].Y;
}

int del = -1;
for (int i = 0; i < 4; i++) {
if ( eq( area(p[i], p[ (i + 1) % 4 ], p[ (i + 2) % 4 ]), 0.0 ) ) {
del = (i + 1) % 4;
}
}

vector<int>who;
if (del == -1) {
// quadrilateral is not of triangular form
m = 4;
for (int i = 0; i < 4; i++) {
who.pb(i);
}
}
else {
// quadrilateral is of triangular form
m = 3;
for (int i = 0; i < 4; i++) {
if (del != i) {
who.pb(i);
}
}
}

// calculate pairwise distance between the vertices of quadrilateral
for (int i = 0; i < who.size(); i++) {
for (int j = 0; j < who.size(); j++) {
given[i][j] = dist(p[who[i] ], p[who[j] ]);
}
}

// consider sides of triangles one by one in all possible order
do {
do {
// new distance matrix where we will compute distance from each vertex to each other
// vertex of configuration formed by the combination of 2 triangles considering
//  their sides in the chosen order.
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 6; j++) {
g[i][j] = 0.0;
}
}

// calculating angle using cosine rule
ld ang1 = angle(l1[0], l1[1], l1[2]);
ld ang2 = angle(l2[0], l2[1], l2[2]);

if ( eq(PI, ang1 + ang2) && eq(l1[0], l2[0]) ) {
// combination of triangle along equal sides generates a triangle as shown
// in the figure above.
n = 3;
// computing pair-wise distances
assign(0, 1, l1[2]);
assign(0, 2, l2[2]);
assign(1, 2, l1[1] + l2[1]);
}
else {
n = 4;
if (eq(l1[0], l2[0]) ) {
// combination of triangle along equal sides generates a quadrangle
// as shown in the figure above.

// computing pair-wise distances
assign(0, 1, l1[2] );
assign(1, 2, l1[1]);
assign(0, 3, l2[2]);
assign(3, 2, l2[1]);
assign(0, 2, l1[0]);
assign(1, 3, side(l1[1], l2[1], ang1 + ang2) );
}

if (eq(PI, ang1 + ang2) ) {
// combination of smaller side of triangle against longer side of
// other traingle to form a quadrangle
bool sw = false;
if (l1[0] > l2[0]) {
sw = true;
swap(l1, l2);
}

assign(0, 1, l2[0] - l1[0]);
assign(1, 2, l1[2]);
assign(2, 3, l1[1] + l2[1]);
assign(3, 0, l2[2]);
assign(1, 3, side(l1[0], l2[1], ang2) );
ld help;
help = angle(l1[0], l1[2], l1[1]);
help = PI - help;
assign(2, 0, side(l1[2], l2[0] - l1[0], help) );
if (sw) {
swap(l1, l2);
}
}
}

// check if the computed pairwise distance for this configuration of triangle is
// equal to the pair wise distances obtained from the given quadrilateral or not.
if ( check() ) {
cout<<"Yes"<<endl;
return ;
}

}
while ( next_permutation(l2.begin(), l2.end() ) );

}
while (next_permutation(l1.begin(), l1.end() ) );

cout<<"No"<<endl;
}


# Time Complexity:

Implementation based

O(1)

# Similiar Problems:

To be updated soon

# Solution:

Setter's solution can be found here
Tester's solution can be found here

Feel free to post comments if anything is not clear to you.

This question is marked "community wiki".

1.7k11730
accept rate: 11%

19.8k350498541

 0 the idea of the solution was naive.but the implementation was a big headache. answered 22 Feb '16, 00:41 534●2●16 accept rate: 12% 3 For you. (22 Feb '16, 00:45) xellos07★ yup I'm a bit slow at implementing codes. (22 Feb '16, 00:57) That's not the point of my comment. I'm just Baneposting. (24 Feb '16, 08:09) xellos07★
 0 Why use law of cosines when one can simply use distance formula. answered 22 Feb '16, 11:57 11 accept rate: 0% 1 There are more than 1 possible ways to accomplish a task. (22 Feb '16, 12:05)
 0 do the figures overlap each other? answered 22 Feb '16, 14:25 1★s6j4_10 18●2 accept rate: 25% They can't as mentioned in the problem statement. Please have a look at the images used in the editorial. (23 Feb '16, 10:37)
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,719
×1,186
×834
×638
×81

question asked: 21 Feb '16, 19:55

question was seen: 1,819 times

last updated: 24 Feb '16, 08:09