December 2005 Problem 'expand' Analysis

If two barns touch, one of them must have a corner on the boundary of the other. So we can identify all cases of two barns touching by iterating over the edges, and for each edge searching for all corners on that edge. We can speed up this process by keeping two lists of corners: one sorted by X then Y, the other sorted by Y then X. To find all the corners on a vertical edge, we need only do two binary searches on the X-then-Y list: one for each end-point of the edges. The corners that lie on the edge will be between these two points in the list.

Any corner can impact on at most four barns, so the number of hits is linear in N. Because of the initial sorting, the entire algorithm is O(N log N).

Here is Bruce's solution:

#include <fstream>
#include <algorithm>
#include <functional>
#include <iterator>

using namespace std;

struct corner {
    int x, y;
    int barn;

    corner() {}
    corner(int x, int y, int barn) : x(x), y(y), barn(barn) {}
};

struct compare_x : public binary_function<corner, corner, bool> {
    bool operator()(const corner &a, const corner &b) const {
        if (a.x != b.x) return a.x < b.x;
        else return a.y < b.y;
    }
};

struct compare_y : public binary_function<corner, corner, bool> {
    bool operator()(const corner &a, const corner &b) const {
        if (a.y != b.y) return a.y < b.y;
        else return a.x < b.x;
    }
};

int main() {
    ifstream in("expand.in");
    ofstream out("expand.out");

    int N;
    in >> N;

    bool contact[N];
    int coords[N][4];
    corner corners[N * 4];

    fill(contact, contact + N, false);
    for (int i = 0; i < N; i++) {
        in >> coords[i][0] >> coords[i][1] >> coords[i][2] >> coords[i][3];
        corners[i * 4 + 0] = corner(coords[i][0], coords[i][1], i);
        corners[i * 4 + 1] = corner(coords[i][0], coords[i][3], i);
        corners[i * 4 + 2] = corner(coords[i][2], coords[i][3], i);
        corners[i * 4 + 3] = corner(coords[i][2], coords[i][1], i);
    }

    sort(corners, corners + 4 * N, compare_x());
    for (int i = 0; i < N; i++)
        for (int j = 0; j <= 2; j += 2) {
            corner *f = lower_bound(corners, corners + 4 * N,
                          corner(coords[i][j], coords[i][1], 0), compare_x());
            corner *l = upper_bound(corners, corners + 4 * N,
                          corner(coords[i][j], coords[i][3], 0), compare_x());

            for (corner *k = f; k != l; k++)
                if (k->barn != i) {
                    contact[i] = true;
                    contact[k->barn] = true;
                }
        }

    sort(corners, corners + 4 * N, compare_y());
    for (int i = 0; i < N; i++)
        for (int j = 1; j <= 3; j += 2) {
            corner *f = lower_bound(corners, corners + 4 * N,
                         corner(coords[i][0], coords[i][j], 0), compare_y());
            corner *l = upper_bound(corners, corners + 4 * N,
                         corner(coords[i][2], coords[i][j], 0), compare_y());

            for (corner *k = f; k != l; k++)
                if (k->barn != i) {
                    contact[i] = true;
                    contact[k->barn] = true;
                }
        }

    out << count(contact, contact + N, false) << "\n";
    return 0;
}