Предисловие:
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 секунд на нем же и сдал задачу.