Help with Dp-Problem APARTS

Problem Url: CodeChef: Practical coding for everyone
I am thinking about an approach that may work. The approach looks like this for each (i, j) create a triangle so that all the (i’s, j’s) that I will cover later can be judged in O(#vertices) and also this triangle should have a merge method that merges two triangles into a bigger polygon and returns its vertices but this approach is lengthy.

Can somebody push me in the recursive direction instead, please?

Is there anything nice that happens if we process the queries in reverse?