Ломаная

Можно развернуть систему координат на 45 градусов, тогда каждое звено ломаной будет параллельно одной из осей координат. Будем заметать вертикальной прямой слева направо и для каждого горизонтального отрезка создадим 2 события (начало и конец), а для вертикального - одно(проходим через него). Из условия видно, что 2 горизонтальных и 2 вертикальных отрезка между собой пересекаться не могут. Значит, все пересечения возможны только между одним вертикальным и одним горизонтальным отрезком. Значит, когда мы доходим до вертикального отрезка, нам нужно знать, сколько горизонтальных отрезков начались, но еще не закончились и в то же время, лежат в нужном диапазоне y-координат. Для этого, можно создать сумматор и для каждого у-ка хранить сколько начатых и еще не законченных отрезков с таким у-ком. Если координаты большие, то в начале следует сделать сжатие координат.
Сложность выходит O(NlogN) на сортировку и O(NlogN) на заметание, т.е. и суммарная сложность O(NlogN).