P9125题解
快斗游鹿
·
·
题解
思路：
题目中有提到，一头牛总是有可能在所有牧场之间穿梭，也就是说一头牛从任意一个放牧地点出发，都能在所有牧场之间穿梭。
那么考虑将每次吃草事件按 t 从小到大排序。一头牛的不在场证明成立，仅当它无法在所有牧场与自己的不在场证明地点之间穿梭。假设某头牛在第 t_i 时刻有不在场证明，离 t_i 最近且早于 t_i 的吃草事件的时刻为 k_1，离 t_i 最近且晚于 t_i 的吃草事件的时刻为 k_2。分析一下会发现，只要它不可能在 (t_i-k_1) 的时间内从上一次吃草事件发生地点赶到不在场证明地点，或不可能在 (k_2-t_i) 的时间内从不在场证明地点赶到下一次吃草事件发生地点，它的不在场证明就成立。
那么问题就变成了，找到比不在场证明时间早的最晚发生的吃草事件。因为吃草事件已经按发生顺序排序，所以这次吃草事件的下一次吃草事件就是比不在场证明时间晚的最早发生的吃草事件。该如何找到这次吃草事件呢？可以很容易地想到二分。那么问题也就迎刃而解了。
一些需要注意的：
$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;
}
```