могут ли сигареты накладываться друг на друга?
например:

0 0 0 2
0 1 0 3

да
Читай Кормен! (и плюс http://e-maxx.ru/algo/intersecting_segments )

спасибо конечно за совет, но я знаю что эта задача есть и в Кормене и на емаксе. Я просто уточнял могут ли отрезки накладываться