Could someone please give me an explanation on how to solve problem F of SWERC 2014? https://speedyguy17.info/icpc/data/swerc/2014/problemset.pdf

It is a computational geometry problem. I can only solve it in O(n²), but O(n log n) solution is required.

-- Also, if blog posts are not the right place to ask help for problems, I would appreciate if someone could inform me some link or forum to get help, since I constantly get stuck on not-so-easy problems like this.

Hi,
I'm solving problem K of this contest:
http://maratona.ime.usp.br/primfase19/provas/competicao/maratona_en.pdf
and I know it can be solved with fast matrix exponentiation.

I got to the step where I have the following two recurrences:

$$$f(1) = 1$$$
$$$f(2) = 6$$$
$$$f(n) = 2^{n-1}+2f(n-1)+4f(n-2) \qquad \forall n > 2$$$

$$$g(3) = 4$$$
$$$g(n) = 4f(n-2)+2g(n-1) \qquad \forall n > 3$$$

The result for input $$$n$$$ is $$$4f(n) + 2g(n)$$$, when n > 2.
But I have no idea how to find matrices to compute such recurrences.

Could someone please suggest me a good reference from where I can learn to find the correct matrices when solving matrix exponentiation problems?