Stuck in a Rut (USACO Silver 2020 December)

只有向东和向北走的牛之间互相会有阻挡的关系，所以们只需要枚举所有向东和向北的奶牛对就可以了。

枚举的时候我们按从西向东（北向牛）和从南往北（东向牛）的顺序进行，如果一头牛已经停止，那么在后续的循环中就不需要处理了。这样就可以保证两两处理一遍，就能得到所有结果。

难度不大，具体见代码。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
int n;
struct C {
    int id;
    int x, y;
    int by;     // stopped by which cow
};
C ecows[1005];
C ncows[1005];
int ecnt, ncnt;
C *cows[1005];
int blames[1005];
 
bool xcmp(C &a, C &b) {return a.x < b.x;}
bool ycmp(C &a, C &b) {return a.y < b.y;}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        char d[10];
        int x,y;
        scanf("%s %d %d", d, &x, &y);
        if (d[0] == 'E') {
            ecows[ecnt++] = {i, x, y, -1};
        } else {
            ncows[ncnt++] = {i, x, y, -1};
        }
    }
    sort(ecows, ecows+ecnt, ycmp);      // sort E cows by y
    sort(ncows, ncows+ncnt, xcmp);      // sort N cows by x
    for (int i = 0; i < ecnt; i++)
        cows[ecows[i].id] = &ecows[i];
    for (int i = 0; i < ncnt; i++)
        cows[ncows[i].id] = &ncows[i];
 
    for (int i = 0; i < ncnt; i++)
        for (int j = 0; j < ecnt; j++) {
            if (ecows[j].by != -1)
                continue;       // this E cow is already stopped by N cows on the west
            int x = ncows[i].x;
            int y = ecows[j].y;
            int dx = x - ecows[j].x;
            int dy = y - ncows[i].y;
            int m = min(dx, dy);
            if (dx >= 0 && dy >= 0 && dx != dy) {
                // 2 cows collide
                if (dx < dy) {
                    // N cow is stopped
                    ncows[i].by = ecows[j].id;
                    break;
                } else {
                    // E cow is stopped
                    ecows[j].by = ncows[i].id;
                }
            }
        }
 
    // count blames
    for (int i = 0; i < n; i++) {
        int id = i;
        // printf("%d\n", id);
        while (cows[id]->by != -1) {
            if (cows[id]->id != id) {
                printf("cows[%d]->id=%d\n", id, cows[id]->id);
                return 0;
            }
            id = cows[id]->by;
            // printf("  %d\n", id);
            blames[id]++;
        }
    }
    for (int i = 0; i < n; i++)
        printf("%d\n", blames[i]);
 
    return 0;
}