Предисловие:

1) На одном из раундов CF я получил TL на халявной задаче и не смог его отладить, несмотря на то что асимптотика решения была O(NlogN), что влезало в LT

2) На одном из туров в ЛКШ у меня не прошла задача на тупое построение выпуклой оболочки за O(NlogN), что влезало в TL.

Итак, я был зол...

В первой задаче в итоге мне хватило только random-а в QSort-е. Но со второй не так-то уж все и просто оказалось.

Что же я сделал?

о1) Будем передавать все параметры по ссылке, а не по значению. (var или const)

о2) Будем делать рандомизтрованный QSort

о3) Магия: вместо свопанья структурок будем свопать отдельные поля! (Если убрать остальные оптимайзы, и оставить только о3 все проходит!

о4) Т.к. TL критичен, избавимся от лишних вызовов "быстрых" {O(1)} функций.

o5) функции "в одну строчку" типа подсчета скалярного произведения выкиним вообще и будем каждый раз вычислять в длинных формулах.

Вот так с 1.006 секунд на тесте, на котором я получал TL, я получил 0.010 секунд на нем же и сдал задачу.