My graph consists of vertexes, which are points, that allow diagonal crossing. Edge (a, b) exists if and only if (a) strictly south-west from (b). Since graph is built, simple dfs easily helps solve the problem ( length of the longest path in the graph - it's diagonal part of result path ).
To avoid TLE#10 in this approach, memorization should be used.

I know, it's not the best approach, but since constraints are relatively low, it does work.
My AC - 0.015    164 КБ.
I think, Longest increasing subsequence - is better in general case.

how you use longest increasing subsequence in this problem ?

Thanks, it helped me) I added functools.lru_cache() decorator for my Python program and got AC :)

Shouldn't we use bfs as we require the shortest path?