Spoj Anttt – CPP solution

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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *