You are not logged in. Please login at www.codechef.com to post your questions!

×

TUZTRN - Editorial

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][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;
// 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[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

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.

This question is marked "community wiki".

asked 21 Feb '16, 19:55

ma5termind's gravatar image

3★ma5termind
1.7k11730
accept rate: 11%

edited 22 Feb '16, 00:36

admin's gravatar image

0★admin ♦♦
19.8k350498541


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

link

answered 22 Feb '16, 00:41

prrateekk's gravatar image

3★prrateekk
534216
accept rate: 12%

3
(22 Feb '16, 00:45) xellos07★

yup I'm a bit slow at implementing codes.

(22 Feb '16, 00:57) prrateekk3★

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

(24 Feb '16, 08:09) xellos07★

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

link

answered 22 Feb '16, 11:57

iamayushanand's gravatar image

2★iamayushanand
11
accept rate: 0%

1

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

(22 Feb '16, 12:05) ma5termind3★

do the figures overlap each other?

link

answered 22 Feb '16, 14:25

s6j4_10's gravatar image

1★s6j4_10
182
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) ma5termind3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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