**Problem Link:** contest, practice

**Difficulty:** Medium-Hard

**Pre-requisites:** Z-Buffering, 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**. So, we should check if point

_{1}P_{2}P_{3}**T**lays in our triangle. There are a lot of ways of doing this. I.e. you can check if

**S(P**, where

_{1}, P_{2}, P_{3}) = S(T, P_{2}, P_{3}) + S(P_{1}, T, P_{3}) + S(P_{1}, P_{2}, T)**S(A, B, C)**equals to the square of triangle

**ABC**.

Here is a pseudocode, that shows the implementation of the algorithm described above.

```
for X from 0 to 319 do
begin
for Y from 0 to 239 do
begin
COLOR = 0
MAX_Z< = -INFINITY
for i from 0 to M do
begin
P_1, P_2, P_3 - points of i'th triangle
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)
Z = Z = -(D - AX - BY) / C
T - point with the coordinates(X, Y, Z)
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) do
begin
if Z > MAX_Z do
begin
COLOR = the color of i'th triangle
MAX_Z = Z
end
end
end
print( COLOR )
end
end
```

The total complexity is **O(N * MAX _{X} * MAX_{Y})**.

**Setter’s Solution:** link

**Tester’s Solution:** link