自动搬运

查看原文

来自洛谷，原作者为

	快斗游鹿 /bx

搬运于2025-08-24 22:45:35，当前版本为作者最后更新于2023-02-26 19:33:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

思路：

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

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

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

一些需要注意的：

$1.$ 题目中的距离指的是欧几里得距离，而非曼哈顿距离。

$2.$ 本题对精度要求很高。

$3.$ 如果某个不在场证明时间比所有吃草事件都早或都晚，那么需要特判。

代码：

#include<bits/stdc++.h>
#define int long long
#define double long double
using namespace std;
const int N=1e5+5;
struct edge{
	int x,y,t;
}e[N];
int g,n,ans;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
bool cmp(edge XXX,edge YYY){
	return XXX.t<YYY.t;
}
signed main(){
	g=read();n=read();
	for(int i=1;i<=g;i++){
		e[i].x=read();e[i].y=read();e[i].t=read();
	}
	sort(e+1,e+1+g,cmp);//排序
	while(n--){
		double xxx,yyy,ttt;cin>>xxx>>yyy>>ttt;
		int l=1,r=g,I=0;
		while(l<=r){//二分
			int mid=(l+r)>>1;
			if(e[mid].t<=ttt)I=mid,l=mid+1;
			else r=mid-1;
		}
		double total;
		if(!I){
			total=sqrt((double)(xxx-e[I+1].x)*(xxx-e[I+1].x)+(yyy-e[I+1].y)*(yyy-e[I+1].y));
			//cout<<total<<endl;
            if(total>(e[I+1].t-ttt))ans++;
		}
		else if(I==g){
			total=sqrt((double)(xxx-e[I].x)*(xxx-e[I].x)+(yyy-e[I].y)*(yyy-e[I].y));
			//cout<<total<<endl;
            if(total>(ttt-e[I].t))ans++;
		}
		else{
			int cnt=0;
			total=sqrt((double)(xxx-e[I+1].x)*(xxx-e[I+1].x)+(yyy-e[I+1].y)*(yyy-e[I+1].y));
			//cout<<total<<endl;
            if(total>(e[I+1].t-ttt))cnt++;
			total=sqrt((double)(xxx-e[I].x)*(xxx-e[I].x)+(yyy-e[I].y)*(yyy-e[I].y));
			//cout<<total<<endl;
            if(total>(ttt-e[I].t))cnt++;
			if(cnt)ans++;
		}
	}
	cout<<ans;
	return 0;
}