TUZTRN - Editorial

cook67
editorial
geometry
implementation
maths

#1

Problem Link:

Practice
Contest

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

Difficulty:

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.
alt text

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

alt text
alt text

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]** = g**[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* ][ perm[j] ], given*[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* ][ perm[j] ], given*[j]) ) {
				ok = false;
			}
		}
	}
	if (ok) {
		return true;
	}
  }
  return false;
}

void solve() {
pair<ld, ld>a, b, c;
// reading first triangle
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

// reading second 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() );

// reading quadrilateral
for (int i = 0; i < 4; i++) {
	cin>>p*.X>>p*.Y;
}

int del = -1;
for (int i = 0; i < 4; i++) {
	if ( eq( area(p*, 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*[j] = dist(p[who* ], 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*[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

Space Complexity:

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.


#2

the idea of the solution was naive.but the implementation was a big headache.


#3

Why use law of cosines when one can simply use distance formula.


#4

do the figures overlap each other?


#5

For you.


#6

yup I’m a bit slow at implementing codes.


#7

There are more than 1 possible ways to accomplish a task.


#8

They can’t as mentioned in the problem statement. Please have a look at the images used in the editorial.


#9

That’s not the point of my comment. I’m just Baneposting.