Square Pasture (USACO Gold 2020 December)

首先注意几个重要条件：

要找的是正方型（我最初读成了长方型...），所以基本是 $N^3$ 的复杂度（一个出发点 $N^2$ ，再加尺寸）。主要的难度是在怎样保证数集合不重不漏。
所有 $x$ 坐标不相同， $y$ 坐标不相同，这个也比较友好，不需要处理一行一列上有多个点的情况，这也是经常会有的条件，需要注意。

要想将所有集合能做有效的划分，然后分类数出来，主要是要找到划分的办法。经常用的办法就是固定某一维坐标，这里还是比较容易想到，将所有点按 $x$ 排序，然后两端点 $a$ 和 $b$ 作为窗口的最左点和最右点，就得到正方型的左右边。现在我们需要找到以 $x_a$ , $x_b$ 为左右 $x$ 边界，并包含 $a$ 和 $b$ 的所有正方型，能够覆盖的不同的cow集合的数量 $C_{ab}$ 。

这时，以 $a$ , $b$ 为顶点的长方形的形状有两种，一种是宽比高大，一种是高比宽大，就时比较关键的一个想法，就是只用处理一种，然后另外一种情况把图转90度来处理（就是交换 $x$ 和 $y$ ），把结果加起来就行。当然特殊情况是宽和高一样，我们需要在结果中再剪掉高宽相等时的数量的一半，就得到总和。

容易看到考虑这两种形状之后，所有的 $C_{ab}$ 之间没有重复计算，也没有遗漏，所以所有 $C_{ab}$ 的和，就是我们要的结果。

下面考虑具体计数：当宽大于等高的时候，要想包含a,b而且是一个正方型（ $x$ 范围 $[x_a, x_b]$ ， $y$ 范围 $[y, y+s]$ ， $s=x_b-x_a$ ），我们容易算出 $y$ 的取值范围 $[\max(y_a,y_b)-s, \min(y_a,y_b)]$ ，在这个范围内做sliding window，就可以统计数量了。这个sliding windows细节比较多，见下面代码，主要思想就是每次将 $y$ 移动一个delta，这个是让有cow从上方进入square，或者有cow从下方离开sqaure（或者同时进入或离开）的最小delta，一共有多少个不同的y的值，就是有多少个不同的集合。

复杂度是 $\mathcal{O}(N^3 \log N)$ 。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pi;
 
int n, ans, eq;
pi cows[205];
#define f first
#define s second
const int INF = 1e9;
 
void solve() {
    sort(cows, cows + n);
    for (int a = 0; a < n; a++) {
        set<int> YS;
        YS.insert(cows[a].s);
        for (int b = a+1; b < n; b++) {
            int sz = cows[b].f - cows[a].f;     // size of the square
            YS.insert(cows[b].s);
            vector<int> ys(YS.begin(), YS.end());
            int ht = abs(cows[b].s - cows[a].s);
            if (ht > sz) continue;              // height <= width
            int ymin = min(cows[a].s, cows[b].s), ymax = max(cows[a].s, cows[b].s), y1, y2;
            int y = max(cows[a].s, cows[b].s) - sz; // y range is [y,y+sz]
            int i = 0, j = 0;                   // i: next out-going cow, j next incoming cow 
            while (1) {
                ans++;
                // move y up one step to include cows or exclude cows
                while (i < ys.size() && ys[i] < y) i++;
                y1 = min(ymin, ys[i]);
                while (j < ys.size() && ys[j] <= y+sz) j++;
                y2 = max(ymax, ys[j-1]);
                if (y2-y1 == sz) eq++;      // squares got counted twice 
                int dy = INF;
                if (i < ys.size()) dy = ys[i]-y+1;
                if (j < ys.size()) dy = min(dy, ys[j]-(y+sz));
                if (dy == INF || y == ymin) break;
                y += dy;
                if (y > ymin) break;
            }
        }
    }
}
 
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
        scanf("%d %d", &cows[i].f, &cows[i].s);
    ans = n+1;      // 0和1个cow组成的集合数量
 
    solve();
    for (pi &c: cows) swap(c.f,c.s);
    solve();
 
    printf("%d", ans-eq/2);
    return 0;
}