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