PROBLEM LINK:
Author: Misha Chorniy
Tester: Tuan Anh Tran Dang
Translators: Sergey Kulik (Russian), Team VNOI (Vietnamese) and Hu Zecong (Mandarin)
Editorialist: Tuan Anh Tran Dang
DIFFICULTY
HARD
PREREQUISITE
NONE
PROBLEM
Check whether 4 triangles can be joined to create one single triangle.
SOLUTION
I guess some of you might expected some nice and short solution for this problem but unfortunately I don’t know one. This problem is just about considering all possible cases and implement them correctly. I underestimated the difficulty of this problem and missed quite a few cases before discussed with the problem setter.
Let’s first consider a simple version of the problem with 2 or 3 triangles.
2 triangles problem
The only way to join two triangles is to pick the common side and checking whether the two joined angles can make 180 degree (see picture).
3 triangles problem
With 3 triangles we can first create a triangle from 2 of them and them try to combine the newly created triangle with the remaining. However this is not cover all possibilities (please take a look at the below picture).
This combination is not so hard to test. You just need to find 3 pairs of common sides and make sure the 3 joined angles can make 360 degree.
sub-case 1
With the mentioned two sub-problem solved we can clear a major scenarios of this problem in which there is 2 or 3 triangle out of the 4 combined to form a single triangle. We have the following way of combining them:
- (((1 + 2) + 3) + 4)
- ((1 + 1) + 3 + 4) // Note that this is different with the previous case since we join 3 triangles (in which one is created from 1 and 2) at one time.
- ((1 + 2) + (3 + 4))
- ((1 + 2 + 3) + 4)
Note that we should consider all possible permutations of 4 triangles for each cases.
Now we come to the interesting in which we’ll cover the other corner case. I will use picture to express the combination and briefly describe how to detect them.
Assume that we got a configuration {t1, t2, t3, t4} which is 4 triangles in some specific order and orientation. Note that there is 6 possible orientation of a triangles which is corresponding to 3! way of arranging there sides. Let ti.a, ti.b, ti.c are the sides of the triangle ti and ti.A, ti.B, ti.C are the internal angle of its where ti.A is opposite ti.a and ti.B is opposite ti.b and so on.
sub-case 2
condition
t1.c = t2.c
t3.b = t3.b
t4.a = t4.a
t1.B + t2.A + t3.C = 180
t1.A + t2.B + t4.C = 180
t3.A + t2.C + t4.B = 180
sub-case 3
condition
t1.c + t2.c = t4.c
t3.b + t2.b = t1.b
t4.a + t2.a = t3.a
t1.A + t2.A = 180
t3.C + t2.C = 180
t4.B + t2.B = 180
sub-case 4
condition
t1.b = t2.b + t3.b
t2.c = t3.c
t3.a = t4.a
t1.C + t2.C = 180
t2.A + t3.B + t4.C = 180
t1.A + t4.A = 180
I have implemented a solution but unfortunately it isn’t optimized enough to pass the time limit (even though it’s correct). You can still refer to my TLE solution in tester’s solution. The room to optimize is on the backstracking process of case 3, 4, 5. You should have different method for each case and stop as soon as you can see some condition is invalid. You should take a look at the problem setter’s code too.