There are a lot of possible fence combinations to consider - if we simply consider every possible even x-coordinate and every possible event y-coordinate, there would be $500000^2$ different combinations which is far too many.

Let us take an extreme example where there are two cows, one at $(1, 1)$ and the other at $(999999, 999999)$. Note that every even x-coordinate between $2$ and $999998$ yields exactly the same division of cows into quadrants, no matter which y-coordinate we pick. By the same logic, every even y-coordinate between $2$ and $999998$ yields exactly the same division of cows into quadrants.

Therefore, we can make the following observation - if we set the vertical fence at $x=a$ but no cow is placed with an x-coordinate of $a-1$, we can move the vertical fence to $x=a-2$ and still preserve the same division of cows into quadrants. Similarly, if we set the horizontal fence at $y=b$ but no cow is placed with a y-coordinate at $y=b-1$, we can move the horizontal fence to $y=b-2$.

This means that we only need to place vertical fences where $x=a$ and there is a cow with x-coordinate $a-1$, and we only need to place vertical fences where $y=b$ and there is a cow with y-coordinate $b-1$.

This gives us at most ten thousand pairs to try, which is small enough.

Here is my Java code:

import java.io.*;
import java.util.*;
public class balancing {
	public static void main(String[] args) throws IOException {
		// initialize file I/O
		BufferedReader br = new BufferedReader(new FileReader("balancing.in"));
		PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("balancing.out")));
		
		// read in N, we can safely ignore B so we don't actually read the value
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		
		// create arrays to store locations of cows
		// cow i is at point (xLoc[i], yLoc[i])
		int[] xLoc = new int[n];
		int[] yLoc = new int[n];
		for(int i = 0; i < n; i++) {
			// read in location of cow i
			st = new StringTokenizer(br.readLine());
			xLoc[i] = Integer.parseInt(st.nextToken());
			yLoc[i] = Integer.parseInt(st.nextToken());
		}
		// in the absolute worst case, N cows will be in one quadrant
		int ans = n;
		for(int xIndex = 0; xIndex < n; xIndex++) {
			for(int yIndex = 0; yIndex < n; yIndex++) {
				// identify the fence location
				// vertical fence at x=xDiv
				// horizontal fence at y=yDiv
				int xDiv = xLoc[xIndex]+1;
				int yDiv = yLoc[yIndex]+1;
				int upperLeft = 0;
				int upperRight = 0;
				int lowerLeft = 0;
				int lowerRight = 0;
				// identify which quadrant each cows lands in
				for(int i = 0; i < n; i++) {
					if(xLoc[i] < xDiv && yLoc[i] < yDiv) {
						lowerLeft++;
					}
					if(xLoc[i] < xDiv && yLoc[i] > yDiv) {
						upperLeft++;
					}
					if(xLoc[i] > xDiv && yLoc[i] < yDiv) {
						lowerRight++;
					}
					if(xLoc[i] > xDiv && yLoc[i] > yDiv) {
						upperRight++;
					}
				}
				// figure out which region has the most cows
				int worstRegion = 0;
				if(upperLeft > worstRegion) {
					worstRegion = upperLeft;
				}
				if(upperRight > worstRegion) {
					worstRegion = upperRight;
				}
				if(lowerLeft > worstRegion) {
					worstRegion = lowerLeft;
				}
				if(lowerRight > worstRegion) {
					worstRegion = lowerRight;
				}
				// determine if we have found a better pair of fences
				if(worstRegion < ans) {
					ans = worstRegion;
				}
			}
		}
		// print the answer
		pw.println(ans);
		// close output stream
		pw.close();
	}
}