USACO2023 Feb Silver P2 COW-libi 奶牛的证词
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=100001;
int n,g;
struct graze{
ll t,x,y;
};
bool cmp(const graze& x, const graze& y){
return x.t < y.t;
}
vector<graze> allgraze;
bool innocent(const graze& a, const graze& b){
return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)>(a.t-b.t)*(a.t-b.t);
}
int main(){
cin>>g>>n;
for(int i=0;i<g;i++){
graze tgraze;
cin>>tgraze.x>>tgraze.y>>tgraze.t;
allgraze.push_back(tgraze);
}
sort(allgraze.begin(),allgraze.end(),cmp);
int ans=0;
for(int i=0;i<n;i++){
graze tg;
cin>>tg.x>>tg.y>>tg.t;
int bi=upper_bound(allgraze.begin(),allgraze.end(),tg,cmp)-allgraze.begin();
if(bi!=g){//check next
if(innocent(allgraze[bi],tg)){
ans++;
continue;
}
}
if(bi!=0){//check prev
if(innocent(allgraze[bi-1],tg)){
ans++;
continue;
}
}
}
cout<<ans<<endl;
return 0;
}