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.
. . . . . . . . . . . . . . ._._._._._._. . . . . . . . . . . . . | . . . | . . . . | . . . | . . | . . . ._._| . . . |_._._|_. . . | . | . . . | . . . . . . |_._| ._._. | . . . . . . . . . . . . . . . . . .
. . . . . . . . . . ._._._._. . . . . . . . . | . | . . ._| . . |_|_. . . |_| ._. | . . . . . . . . . . . .
#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;
}