Cow-libi

题目描述

注意：本题时间限制为 4s，是默认的两倍。\n有人一直在 Farmer John 的 $(1 \le G \le 10^5)$ 个私人花园里吃草！凭借其专业的取证知识，FJ 已经能够确定每个花园被吃草的精确时间。他还确定所有吃草事件都由同一头奶牛所为。\n\n针对这些“犯罪”，FJ 的 $N$ 头奶牛 $(1 \le N \le 10^5)$ 各自提供了一份不在场证明，证明该奶牛在某一时刻位于某一特定地点。请帮助 FJ 判断每一份不在场证明是否能够证明该奶牛无罪。\n\n如果一头奶牛不可能在所有吃草事件与她的不在场证明之间完成行程，则可以判定她无罪。奶牛的移动速度为每单位时间移动 1 单位距离。

输入格式

第一行包含用空格分隔的 $G$ 和 $N$。\n接下来的 $G$ 行，每行包含整数 $x$, $y$, $t$，用空格分隔，满足 $(-10^9 \le x, y \le 10^9; 0 \le t \le 10^9)$，描述一次吃草事件的位置与时间。保证总是存在一头奶牛可以在所有吃草事件之间移动。\n接下来的 $N$ 行，每行包含 $x$, $y$, $t$，用空格分隔，满足 $(-10^9 \le x, y \le 10^9; 0 \le t \le 10^9)$，描述每头奶牛的不在场证明的位置与时间。

输出格式

输出一个整数：其不在场证明能够证明无罪的奶牛数量。

2 4\n0 0 100\n50 0 200\n0 50 50\n1000 1000 0\n50 0 200\n10 0 170

2

提示

共有两次吃草事件；第一次在时间 $100$ 于 $(0, 0)$，第二次在时间 $200$ 于 $(50, 0)$。\n第一头奶牛的不在场证明不能证明她无罪。她恰好有足够的时间赶到第一次吃草地点。\n第二头奶牛的不在场证明能够证明她无罪。她离所有吃草地点都非常远。\n不幸的是，对第三头奶牛而言，出现在案发现场并不能证明无罪。\n最后，第四头奶牛是无罪的，因为从她的不在场证明出发不可能及时赶到最后一次吃草地点。\nSCORING:\n输入 2-4：$1 \le G, N \le 10^3$。此外，对吃草事件与不在场证明，$-10^6 \le x, y \le 10^6$ 且 $0 \le t \le 10^6$。\n输入 5-11：无额外限制。\n题目致谢：Mark Gordon

标签: USACO|2023|Silver

来源

USACO|2023|Silver