(Analysis by Benjamin Qi)

First, compress all of the $x$ and $y$ coordinates so that everything is in the range $[0,N-1]$.

For each nonempty subset of cows that can be fenced off, consider the rectangle of the minimum size that encloses the subset. This rectangle must contain a cow on each of its four sides. Conversely, each rectangle with a cow on each of its sides corresponds to a unique subset of cows that can be fenced off. Due to the condition that all coordinates are distinct, each side will contain exactly one cow.

A naive approach would be to test whether each of the $\mathcal{O}(N^4)$ possible rectangles satisfies this condition, giving an $\mathcal{O}(N^5)$ time solution. For additional an $\mathcal{O}(N^4)$ time solution, check each rectangle in $\mathcal{O}(1)$ time.

For full credit, we need an $\mathcal{O}(N^2)$ solution. Suppose that we fix the cows $a=(x_a,y_a)$ and $b=(x_b,y_b)$ on the bottom and top sides of the rectangle (so $y_a\le y_b$). Then the cow $c$ on the left side of the rectangle must satisfy $x_c\le \min(x_a,x_b)$ and $y_a\le y_c\le y_b$. Similarly, the cow $d$ on the right side of the rectangle must satisfy $\max(x_a,x_b)\le x_d$ and $y_a\le y_d\le y_b$. In other words, the number of possibilities for $c$ is the number of points in the rectangle $[0,\min(x_a,x_b)]\times [y_a,y_b]$ while the number of possibilities for $d$ is the number of cows in the rectangle $[\max(x_a,x_b),N-1]\times [y_a,y_b]$. We can compute these quantities using 2D prefix sums.

Brian Dean's code:

#include <iostream>
#include <algorithm>
using namespace std;

typedef pair<int,int> Point;
bool ycomp(Point p, Point q) { return p.second < q.second; }

const int MAX_N = 2500;
int N, Psum[MAX_N+1][MAX_N+1];
Point P[MAX_N];

int rsum(int x1, int y1, int x2, int y2)
{
return Psum[x2+1][y2+1] - Psum[x2+1][y1] - Psum[x1][y2+1] + Psum[x1][y1];
}

int main(void)
{
cin >> N;
for (int i=0; i<N; i++) {
int x, y;
cin >> x >> y;
P[i] = make_pair(x,y);
}
sort(P, P+N);
for (int i=0; i<N; i++) P[i].first = i+1;
sort(P, P+N, ycomp);
for (int i=0; i<N; i++) P[i].second = i+1;
for (int i=0; i<N; i++) Psum[P[i].first][P[i].second] = 1;
for (int i=1; i<=N; i++)
for (int j=1; j<=N; j++)
Psum[i][j] += Psum[i-1][j] + Psum[i][j-1] - Psum[i-1][j-1];
for (int i=0; i<N; i++)
for (int j=i; j<N; j++) {
int x1 = min(P[i].first, P[j].first) - 1;
int x2 = max(P[i].first, P[j].first) - 1;
}
cout << answer + 1 << "\n";

}


Danny Mittal's code:

import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;

public class RectangularPasture {
static int[][] sums;

static int getSum(int fromX, int toX, int fromY, int toY) {
return sums[toX][toY] - sums[fromX - 1][toY] - sums[toX][fromY - 1] + sums[fromX - 1][fromY - 1];
}

public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[] xs = new int[n];
int[] ys = new int[n];
Integer[] cows = new Integer[n];
for (int j = 0; j < n; j++) {
xs[j] = in.nextInt();
ys[j] = in.nextInt();
cows[j] = j;
}
Arrays.sort(cows, Comparator.comparingInt(j -> xs[j]));
for (int x = 1; x <= n; x++) {
xs[cows[x - 1]] = x;
}
Arrays.sort(cows, Comparator.comparingInt(j -> ys[j]));
for (int y = 1; y <= n; y++) {
ys[cows[y - 1]] = y;
}
sums = new int[n + 1][n + 1];
for (int j = 0; j < n; j++) {
sums[xs[j]][ys[j]]++;
}
for (int x = 0; x <= n; x++) {
for (int y = 0; y <= n; y++) {
if (x > 0) {
sums[x][y] += sums[x - 1][y];
}
if (y > 0) {
sums[x][y] += sums[x][y - 1];
}
if (x > 0 && y > 0) {
sums[x][y] -= sums[x - 1][y - 1];
}
}
}
long answer = n + 1;
for (int j = 0; j < n; j++) {
for (int k = j + 1; k < n; k++) {
answer += getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]), 1, Math.min(ys[j], ys[k]))
* getSum(Math.min(xs[j], xs[k]), Math.max(xs[j], xs[k]), Math.max(ys[j], ys[k]), n);
}
}