USACO23FEB-Silver B

题目来源（From）

洛谷： USACO23FEB-Silver Cow Libi(B)

SPOJ：USACO23FEB-Silver Cow Libi(B) - 题面

题解： USACO23FEB-Silver Cow Libi(B) - 题解

题目（Problem）

题目描述（中文）

$\qquad$农民约翰发现有人在他的 $G \ (1≤G≤10^5)$个牧场进行非法放牧。约翰利用他的法医专业知识，能够确定每个牧场被放牧的精确时间。

$\qquad$对于这些罪行，$N (1≤N≤10^5)$ 头嫌疑奶牛中的每一头牛都提供了自己不在场证词，证词说明了该牛在特定时间出现在特定位置。帮助约翰测试这些有不在场证明的母牛是否是无辜的。

$\qquad$奶牛们会按照放牧时间依次经过每个牧场。

$\qquad$如果一头母牛不可能在所有的牧场和她的证词提供的地点之间旅行，那么母牛便是无辜的。一头奶牛可以在单位时间内以 $1$ 单位距离的速度移动。

$\qquad$请你求出有多少奶牛是无辜的？

$\qquad$数据保证至少存在一头牛不是无辜的。

输入格式

$\qquad$输第一行将包含两个整数 $G$ 和 $N$ 。

$\qquad$接下来的 $G$ 行，每行包含三个整数 $x,y,t \ (- 10^9≤x,y≤10^9,0≤t≤10^9)$ ，描述约翰掌握的非法放牧的牧场位置和时间。

$\qquad$接下来的 $N$ 行，每行包含 $x,y,t \ (- 10^9≤x,y≤10^9,0≤t≤10^9) $ ，描述一头牛提供的不在场证词：自己所在位置和时间。

输出格式

$\qquad$输出一行一个整数，表示清白的牛的数量。

样例

输入数据 1

2 4
0 0 100
50 0 200
0 50 50
1000 1000 0
50 0 200
10 0 170

输出数据 1

样例1说明

$\qquad$约翰发现有两次非法放牧的现场：第一次是 $100$ 时刻在位置 $(0,0)$ ，第二次是 $200$ 时刻在位置 $(50,0)$ 。

$\qquad$第一头母牛的不在场证明并不能证明她的清白，因为她有足够的时间到达第一个牧场。

$\qquad$第二只母牛的不在场证明了她的清白，因为她根本不在牧场附近。

$\qquad$不幸的是，第三头牛出现在犯罪现场并不能证明它是无辜的。

$\qquad$最后，第四头牛是无辜的，因为不可能及时从她的证词描述的地点达到最后的牧场。

数据规模与约定

测试点 $2-4$：$1 \le G,N \le 10^3$；此外，对于在现场和不在场证明，$−10^6 \le x,y \le 10^6$ 且 $0 \le t \le 10^6$。
测试点 $5-11$：没有其它约定。

题解（Solution）

$\qquad$这道题的题意翻译很有问题，作者在此处已更正。

$\qquad$由于太简单，就不想写题解，直接搬运过来：

$\qquad$题目中有提到，一头牛总是有可能在所有牧场之间穿梭，也就是说一头牛从任意一个放牧地点出发，都能在所有牧场之间穿梭。

$\qquad$那么考虑将每次吃草事件按 tt 从小到大排序。一头牛的不在场证明成立，仅当它无法在所有牧场与自己的不在场证明地点之间穿梭。假设某头牛在第 $t_{i}$ 时刻有不在场证明，离 $t_{i}$ 最近且早于 $t_{i}$ 的吃草事件的时刻为 $k_{1}$ ，离 $t_{i}$ 最近且晚于 $t_{i}$ 的吃草事件的时刻为 $k_{2}$ 。分析一下会发现，只要它不可能在 $\left(t_{i}-k_{1}\right)$ 的时间内从上一次吃草事件发生地点赶到不在场证明地点，或不可能在 $\left(k_{2}-t_{i}\right)$ 的时间内从不在场证明地点赶到下一次吃草事件发生地点，它的不在场证明就成立。

$\qquad$那么问题就变成了，找到比不在场证明时间早的最晚发生的吃草事件。因为吃草事件已经按发生顺序排序，所以这次吃草事件的下一次吃草事件就是比不在场证明时间晚的最早发生的吃草事件。该如何找到这次吃草事件呢? 可以很容易地想到二分。那么问题也就迎刃而解了。

一些需要注意的地方：

题目中的距离指的是欧几里得距离，而非曼哈顿距离。
本题对精度要求很高。
如果某个不在场证明时间比所有吃草事件都早或都晩，那么需要特判。

代码（Code）

我的代码

#include<bits/stdc++.h>
#include<stack>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define double long double
#define int long long
#define Fi first
#define Se second
inline double input(){double x;return cin>>x,x;}
const int N = 101234;
int g,n;
struct T{
	double x,y,t;
	bool operator<(const T y){return t<y.t;}
}cow[N],pla[N];
bitset<N> ava;

inline double dis(double x1,double y1,double x2,double y2){return sqrt((double)(x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}

inline bool check(T a,T b,double lmt){return lmt<dis(a.x,a.y,b.x,b.y);}

signed main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	string str("b");
	freopen((str+".in").c_str(),"r",stdin);
	freopen((str+".out").c_str(),"w",stdout);
	cin>>g>>n;
	For(i,1,g) pla[i]={input(),input(),input()};
	sort(pla+1,pla+g+1);
	For(i,1,n){
		cow[i]={input(),input(),input()};
		int pos1=lower_bound(pla+1,pla+g+1,cow[i])-pla;
		int pos2=pos1-1;
		if(1<=pos1 && pos1<=g) ava[i]=ava[i]|check(cow[i],pla[pos1],abs(pla[pos1].t-cow[i].t));
		if(1<=pos2 && pos2<=g) ava[i]=ava[i]|check(cow[i],pla[pos2],abs(pla[pos2].t-cow[i].t));		
	}cout<<ava.count()<<'\n';
	return 0; 
}