The problem is simple. You are given N point and M query. Each query will provide 4 points. you need to create two segments with first two point and second two point. And add their intersecting point to the tail of the given list of point. query will be always valid. You have to ans in which query the intersecting point is (0,0).

Here is the problem statement : http://poj.org/problem?id=3429 Here is my code: http://ideone.com/2jMgAj

My idea is just to do the simulation. I used this geometry library many time to get AC. I don't know if there is any problem? Some description of my geometry library for you better understanding,

1. Vec -is a point/vector.
2. Line — is a line segement.
3. L1.LineAndLineIntersection2D( line L2 , double t , double s ) — For intersecting two line. t denotes the parametric t of the L1 and s denotes the parametric s of the line L2.
4. L1.atPos(t) — returns the point on the Line L1 according to parametric t.