Solution Notes: In one sentence, this problem boils down to computing the size of a maximum independent set in a bipartite graph. Nodes on the left-hand side of the graph represent horizontal segments, and nodes on the right-hand side represent vertical segments; two nodes are connected if their corresponding segments cross. In this graph, we need to find a maximum independent set -- a set of nodes of maximum size in which no two are connected by an edge (since we cannot select two crossing segments).

The maximum independent set problem in a general graph is actually a _very_ hard problem (NP-hard, and hard even to approximate well), but in a bipartite graph it turns out to be much better behaved. We start with the well-known fact that the maximum s-t flow equals the minimum s-t cut capacity in any graph. In a bipartite graph, this statement tells us that size of a maximum matching (comparable to a maximum flow) is equal to the size of a minimum node cover (comparable to a minimum cut), a fact sometimes known a Konig's theorem. A minimum node cover is a selection of the minimum possible number of nodes so that every edge has at least one of its endpoints covered by the set. This problem is usually NP-hard, but in bipartite graphs it can be solved via max flow techniques since a minimum node cover can be derived easily from a minimum cut. The final piece of our puzzle is that a maximum independent set in any graph can be obtained by taking the complement of a minimum node cover (i.e., by taking the nodes not in the minimum node cover). The complement C' of a node cover C is an independent set since if it was not, and there was some edge e whose endpoints were both included in C', then e would not have been covered by C. Likewise, the compliment of S' of an indepenent set S is a node cover, since if it was not, and there was some edge e uncovered in S', then both endpoints of e would have been included in S, making it not an independent set. Therefore, the answer to this problem is to take the total number of nodes minus the size of a maximum matching. The code in the solution below is therefore essentially just the code to compute a maximum matching.



#include <cstdio>
#include <cstring>
#include <vector>
#include <cassert>
using namespace std;

const int MAXN = 10005;

struct DfsMatch
{
    const static int MAXA = MAXN, MAXB = MAXN, INF = 1000000005;

    int A, B, elast [MAXA];
    int start, vis [MAXA], prev [MAXB];
    vector <int> eadj, eprev;

    inline DfsMatch ()
    {
        A = B = -1;
    }

    inline void init (int a, int b)
    {
        A = a; B = b;
        memset (elast, -1, A * sizeof (int));
        eadj.clear ();
        eprev.clear ();
    }

    inline void addedge (int a, int b)
    {
        eadj.push_back (b); eprev.push_back (elast [a]); elast [a] = eprev.size
() - 1;
    }

    bool dfs (int num)
    {
        if (vis [num] == start)
            return false;

        vis [num] = start;

        for (int i = elast [num]; i != -1; i = eprev [i])
            if (prev [eadj [i]] == -1)
            {
                prev [eadj [i]] = num;
                return true;
            }

        for (int i = elast [num]; i != -1; i = eprev [i])
            if (dfs (prev [eadj [i]]))
            {
                prev [eadj [i]] = num;
                return true;
            }

        return false;
    }

    int match ()
    {
        if (A == -1 && B == -1)
            return -INF;

        memset (prev, -1, B * sizeof (int));
        memset (vis, -1, A * sizeof (int));
        int total = 0;

        for (int i = 0; i < A; i++)
        {
            start = i;

            if (dfs (i))
                total++;
        }

        return total;
    }
};

FILE *in = fopen ("steeple.in", "r"), *out = fopen ("steeple.out", "w");

struct hseg
{
    int x1, x2, y;
};

struct vseg
{
    int x, y1, y2;
};

bool intersect (hseg h, vseg v)
{
    return (v.y1 <= h.y && h.y <= v.y2) && (h.x1 <= v.x && v.x <= h.x2);
}

int N, H, V;
hseg horiz [MAXN];
vseg vert [MAXN];
DfsMatch graph;

int main ()
{
    fscanf (in, "%d", &N);
    H = V = 0;

    for (int i = 0; i < N; i++)
    {
        int x1, y1, x2, y2;
        fscanf (in, "%d %d %d %d", &x1, &y1, &x2, &y2);
        assert ((x1 == x2) ^ (y1 == y2));

        if (x2 < x1)
            swap(x1, x2);
        if (y2 < y1)
            swap(y1, y2);

        if (y1 == y2)
            horiz [H++] = (hseg) {x1, x2, y1};
        else
            vert [V++] = (vseg) {x1, y1, y2};
    }

    graph.init (H, V);

    for (int i = 0; i < H; i++)
        for (int j = 0; j < V; j++)
            if (intersect (horiz [i], vert [j]))
                graph.addedge (i, j);

    fprintf (out, "%d\n", N - graph.match ());
    return 0;
}