Link: http://www.spoj.com/problems/ANTTT/

Idea:

Create a graph of the intersecting lines and use dfs/bfs to find whether a path exists from one node to another. For the intersection part there are two possible ways I know:

1) write out equations for the lines and find the formula for the Y (or X) cordinate and then check whether the point is part of the segment. This is however harder and slower to right with some cases to consider. For example the line x=0.

2) just use standard vector operations. If you are given the lines A-B and C-D. Chech whether A is on one side of C-D and if B is on the other. Then check whether C and D are on opposite sides of A-B. In this case they collide. If we also consider the case where one of the points can lie on the segments, then we can to also consider the case: 1 1 3 3, 4 4 5 5. I.e. when they are parallel. Then you have to also check for the bounds.

When I was at high school, I used to write the first technique and it worked out well. I learned about the second while I was doing USACO.

#include <cstdio> #include <iostream> using namespace std; typedef long long ll; struct Point { ll x,y; Point() {}; Point(ll _x, ll _y) : x(_x), y(_y) {}; }; struct Line { Point from,to; Line() {}; Line(const Point & _from, const Point & _to) : from(_from), to(_to) {}; }; Point operator -(const Point & A, const Point & B) { return Point(A.x-B.x, A.y-B.y); } ll cross(const Point & A, const Point & B) { return A.x*B.y - A.y*B.x; } bool onOneSide(const Line & A, const Line & B) { ll v1 = cross(B.from - A.from, A.to - B.from); ll v2 = cross(B.to - A.from, A.to - B.to); if(v1 == 0LL && v2 == 0LL) { if (A.to.x < B.from.x) return false; if (A.from.x > B.to.x) return false; } return (v1 <= 0LL && v2 >=0LL) || (v1 >=0LL && v2 <= 0LL); } bool intersect(const Line & A, const Line & B) { return onOneSide(A,B) && onOneSide(B,A); } int nb[1001][1001]; int nbSz[1001]; int used[1001]; Line lines[1001]; int destination; int q; void dfs(int u) { if (used[u]==q) return; if (destination==-1) return; if (u == destination) destination = -1; used[u] = q; for (int i = 0; i < nbSz[u]; ++i) { dfs(nb[u][i]); } } void cl(int n) { for (int i = 1; i<=n; ++i) nbSz[i]=0, used[i]=0; } void addNb(int A, int B) { nb[A][nbSz[A]++] = B; nb[B][nbSz[B]++] = A; } int main() { int t; scanf("%d",&t); while (t--) { int n,m; scanf("%d%d",&n,&m); for (int i = 0; i < n; ++i) { ll x1,x2,y1,y2; scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2); if (x1 > x2) { swap(x1,x2); swap(y1,y2); } lines[i+1] = Line(Point(x1,y1),Point(x2,y2)); } for (int i = 1; i<=n; ++i) { for (int j = i+1; j<=n; ++j) { if (intersect(lines[i], lines[j])) { addNb(i,j); } } } for (q = 1; q <= m; ++q) { int a,b; scanf("%d%d",&a,&b); destination = b; dfs(a); if (destination == -1) { printf("YESn"); } else { printf("NOn"); } } cl(n); } return 0; }