Solution Notes (Travis Hance): Since all of the fences are either vertical or horizontal, we can view the plane as a discrete graph, with a vertex repsenting a square with vertices (x,y), (x+1,y), (x+1,y+1), and (x,y+1), where x and y are integers. Each vertex is connected to its four neighbors in the square grid, except, of course, when such a neighbor is separated by a fence. Each cow can be assigned to some vertex in this graph (any of the four squares with that cow as a vertex). Then all the cows within a single connected-component of the graph form a community. We can find all the connected-components of the graph using flood-fill.

Technically, this graph of squares is infinitely large, but we can restrict to a rectangle that is just barely large enough to hold all the fences, although it needs to leave room on the sides so that paths can get around the fences. That is, if the minimum and maximum coordinates of the fences are X_min, X_max, Y_min, and Y_max, it suffices to look at a rectangle spanning from X_min - 1 to X_max + 1 lengthwise and from Y_min - 1 to Y_max + 1 heightwise.

```. . . . . . . . . . . . .
. ._._._._._._. . . . . .
. . . . . . . | . . . | .
. . . | . . . | . . | . .
. ._._| . . . |_._._|_. .
. | . | . . . | . . . . .
. |_._| ._._. | . . . . .
. . . . . . . . . . . . .```

Unfortunately, the coordinates of the fence posts can be anywhere in the range 0 .. 1,000,000. That means the graph we consider would need to be very large, over 1,000,0002 vertices. There is a trick to reduce the number of vertices though. If there are N fences (2N endpoints) and C cows, then there are only 2N+C points which are important. For instance, if for some value X none of the important points have x-coordinate X, then we can just remove that column completely without changing the answer. So, we can sort all the important coordinates. We look at the ith smallest such value, and replace every instance of it with i. Then we can make a grid which only of size approximately 2N+C in both width and height. Compressing the above graph in this way gives:

```. . . . . . . . .
. ._._._._. . . .
. . . . . | . | .
. ._| . . |_|_. .
. |_| ._. | . . .
. . . . . . . . .```

Then we can do flood fill in O((N+C)2) time. Here is Johnny Ho's solution, in C++:

``````
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <stack>
using namespace std;

const int inf = 1 << 30;

int x[3010], y[3010];

int t[3010];
int compress(int a[3010], int z) {
memcpy(t, a, sizeof(t));
sort(t, t + z);
int nz = unique(t, t + z) - t;
for (int i = 0; i < z; i++) {
a[i] = (lower_bound(t, t + nz, a[i]) - t) * 2;
}
return nz * 2;
}

int xz, yz;
char arr[6010][6010];

int gz;
int mx[4] = {-1, 0, 1, 0};
int my[4] = {0, -1, 0, 1};

stack<short> sx, sy;
void put(int x, int y) {
if (x < 0 || x >= xz || y < 0 || y >= yz) return;
if (arr[x][y] == 'X') return;
gz += (arr[x][y] == 'C');
arr[x][y] = 'X';
sx.push(x);
sy.push(y);
}

void dfs(int startx, int starty) {
// sx, sy should be empty
put(startx, starty);
while (sx.size()) {
int x = sx.top(); sx.pop();
int y = sy.top(); sy.pop();
for (int i = 0; i < 4; i++) {
int nx = x + mx[i];
int ny = y + my[i];
put(nx, ny);
}
}
}

int main() {
freopen("crazy.in", "r", stdin);
freopen("crazy.out", "w", stdout);
int n, m;
cin >> n >> m;
int z = 0;
x[z] = y[z] = -inf; z++;
x[z] = y[z] = inf; z++;
for (int i = 0; i < 2 * n; i++) {
cin >> x[z] >> y[z]; z++;
}
for (int i = 0; i < m; i++) {
cin >> x[z] >> y[z]; z++;
}
xz = compress(x, z);
yz = compress(y, z);
memset(arr, '.', sizeof(arr));
for (int i = 0; i < n; i++) {
int a = i * 2 + 2;
int b = i * 2 + 3;
int x1 = x[a], y1 = y[a], x2 = x[b], y2 = y[b];
if (x1 == x2) {
if (y1 > y2) swap(y1, y2);
while (y1 <= y2) {
arr[x1][y1] = 'X';
y1++;
}
} else {
if (x1 > x2) swap(x1, x2);
while (x1 <= x2) {
arr[x1][y1] = 'X';
x1++;
}
}
}
for (int i = 0; i < m; i++) {
int a = i + 2 * n + 2;
arr[x[a]][y[a]] = 'C';
}
int ans = 0;
for (int i = 0; i < m; i++) {
int a = i + 2 * n + 2;
gz = 0;
dfs(x[a], y[a]);
ans = max(ans, gz);
}
cout << ans << endl;
}
``````