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;
}
USACO2023 Feb Silver P2 COW-libi 奶牛的證詞的評(píng)論 (共 條)
