Problem Link: contest, practice Difficulty: MediumHard Prerequisites: ZBuffering, Geometry, Stereometry, Implementation Problem: We are given N polygons(triangles and quadrilaterals) in 3D. Our task is to project all of them on the 2D plane. Explanation: Firstly, in our further explanation we'll assume, that triangles are the only polygons that we have(since every quadrilateral can be splited into two triangles). OK, now we have M triangles(N ≤ M ≤ 2N, since each quadrilateral has been splitted into two triangles). Let's fix cell(X,Y). What colour this cell should be coloured with? Intuitively, it should be the color of the triangle, which has the maximal Z for fixed (X,Y). Sounds pretty easy, huh? But the key part of this problem is the implementation part. Let's fix a triangle with vertices P_{1}(X_{1}, Y_{1}, Z_{1}), P_{2}(X_{2}, Y_{2}, Z_{2}), P_{3}(X_{3}, Y_{3}, Z_{3}). Also, let's find a plane, in which triangle P_{1}P_{2}P_{3} lays. Each plane can be defined by an equation AX + BY + CZ + D = 0. Let's find coefficients A, B, C and D. A = Y_{1}(Z_{2}  Z_{3}) + Y_{2}(Z_{3}  Z_{1}) + Y_{3}(Z_{1}  Z_{2}); B = Z_{1}(X_{2}  X_{3}) + Z_{2}(X_{3}  X_{1}) + Z_{3}(X_{1}  X_{2}); C = X_{1}(Y_{2}  Y_{3}) + X_{2}(Y_{3}  Y_{1}) + X_{3}(Y_{1}  Y_{2}); D = X_{1}(Y_{2}Z_{3}  Y_{3}Z_{2})  X_{2}(Y_{3}Z_{1}  Y_{1}Z_{3})  X_{3}(Y_{1}Z_{2}  Y_{2}Z_{1}). If you don’t understand why the coefficient look the way they are, please, visit the following link. So, let's determine the value of Z for triangle P_{1}P_{2}P_{3} at the cell(X, Y)(it's also fixed, remember?). Z = (D  AX  BY) / C. Shall we assume that triangle P_{1}P_{2}P_{3} has the distance Z above the fixed cell? No, we shall not. Well, the plane AX + BY + CZ + D = 0 definitely has the distance Z above the fixed cell, but point T with the coordinates (X, Y, Z) may not belong to our triangle P_{1}P_{2}P_{3}. So, we should check if point T lays in our triangle. There are a lot of ways of doing this. I.e. you can check if S(P_{1}, P_{2}, P_{3}) = S(T, P_{2}, P_{3}) + S(P_{1}, T, P_{3}) + S(P_{1}, P_{2}, T), where S(A, B, C) equals to the square of triangle ABC. Here is a pseudocode, that shows the implementation of the algorithm described above.
The total complexity is O(N * MAX_{X} * MAX_{Y}). Setter's Solution: link Tester's Solution: link
This question is marked "community wiki".
asked 21 Apr '14, 00:16

Hi can anyone explain what onright function in setter's solution is doing ? answered 21 Apr '14, 12:50
It checks if the points satisfy to the righthand rule. http://en.wikipedia.org/wiki/Righthand_rule
(21 Apr '14, 14:22)
