P3114 [USACO15JAN] 坐标离散化 + 扫描线 + Set

题意

传送门 P3114 [USACO15JAN]Stampede

题解

每头牛抵达 $x=0$ 的时间段为 $[(-x)\times r,(-x-1)\times r)$，且每头牛初始横坐标为整数，那么对于 $t\in Z$ 在时间段 $[t,t+1)$ 看到的都是同一头牛，考虑整数的时间点即可。那么按照各头牛抵达 $x=0$ 的时间进行扫描，标记牛穿过 $x=0$ 的左右端点；用一个集合维护当前 $x=0$ 位置的牛，每个整数时间点记录集合中纵坐标最小的牛。

#include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <set> #include <vector> using namespace std; #define maxn 50005 struct cow { int y, id, f; }; struct node { int y, id; bool operator<(const node &b) const { return y < b.y; } }; int N, Y[maxn << 1], T[maxn << 1], id[maxn << 1]; bool seen[maxn], F[maxn << 1]; vector<cow> line[maxn << 1]; set<node> now; int compress(int *x, int n) { vector<int> xs(n); for (int i = 0; i < n; i++) { xs[i] = x[i]; } sort(xs.begin(), xs.end()); xs.erase(unique(xs.begin(), xs.end()), xs.end()); for (int i = 0; i < n; i++) { x[i] = lower_bound(xs.begin(), xs.end(), x[i]) - xs.begin(); } return xs.size(); } int main() { scanf("%d", &N); for (int i = 0; i < N; i++) { int x, y, r; scanf("%d%d%d", &x, &y, &r); Y[i] = Y[i + N] = y; T[i] = (-x) * r, T[i + N] = T[i] - r; id[i] = id[i + N] = i; F[i] = 0, F[i + N] = 1; } int n = N << 1, t = compress(T, n); for (int i = 0; i < n; i++) { line[T[i]].push_back(cow{Y[i], id[i], F[i]}); } for (int i = 0; i < t; i++) { for (int j = 0; j < line[i].size(); j++) { cow &c = line[i][j]; if (c.f) { now.insert(node{c.y, c.id}); } else { now.erase(node{c.y, c.id}); } } if (!now.empty()) { seen[(*now.begin()).id] = 1; } } int res = 0; for (int i = 0; i < N; i++) { res += seen[i]; } printf("%d\n", res); return 0; }