This is a supplementary explanation to the official commentary.

By utilizing the fact that \(C_T\) must form a convex polygon even at intermediate steps and applying appropriate pruning, experimental results suggest that the number of states can be reduced to at most \(N^5/5!\). Therefore, by using a hashmap with the first two vertices of each of the three types as the key, you can achieve sufficiently fast code for dynamic programming.

Implementation Example (C++)

Additionally, the constraints are set in such a way that it is possible to achieve AC (Accepted) even without pruning, if you put in enough effort.