欢迎光临散文网 会员登陆 & 注册

USACO2023 Feb Silver P2 COW-libi 奶牛的证词

2023-06-30 22:02 作者:信奥赛USACO郑老师  | 我要投稿

#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 奶牛的证词的评论 (共 条)

分享到微博请遵守国家法律