I can't success the Test 1.
Who can help me?

Consider point set generated by segments. For example, segments 1-2 and 3-4 generates set of thee points.

Each point should have attribute "parity" with such property: if one point can be reached from another then its parity should be equal.

This model provides criteria of "compatiblity" of the segments set. I have implemented O(n*n) algorithm for this task. You can find some other details about my algorithm at this board.

Maybe Yakovlev have another model? ;)

Edited by author 01.04.2004 21:46

I used the same idea, but my new solution is O(n*log(n)) and worked 0.078 sec.