I think 2 seconds is bad Time Limit. Also I don't know how many input
tests contains each test.
So I tried everything: like binary search and hash-function. But
always TLE.
Do you think 2 seconds is enough time?

There is at least O(n*n) algorithm for 1003.

I solved it in O(n*n) time and get AC in 0.125 sec. So, 2 seconds is enough timelimit for this problem.

My algo is:

Each point have attibutes "parity" and "connectivity compontent number". When processing each segment, we check if it
- form a new connectivity component - O(1)
- extends existing connectivity components - O(1)
- connects existing CCs - O(N) for glue operation
- form a cycle in the existing CC - O(1)

This stage is O(n*n). It's quite enought for AC, but I'm still interested in more efficient algorithm :) Any ideas? :)