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];
  long long answer = 0;
  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;
      answer += rsum(0,i,x1,j) * rsum(x2,i,N-1,j);
    }
  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);
            }
        }
        System.out.println(answer);
    }
}