Cod sursa(job #2036630)

Utilizator andreiutu111Noroc Andrei Mihail andreiutu111 Data 10 octombrie 2017 21:09:05
Problema Grendizer Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.33 kb
#include<fstream>
#include<vector>
#include<algorithm>
#include<math.h>
using namespace std;
ifstream f("grendizer.in");
ofstream g("grendizer.out");
int N,M,dx[9]{0,1,0,-1,1,-1,1,-1},dy[9]={1,0,-1,0,1,-1,-1,1};
long long x,y,r;
vector < pair<long long,long long> > ob;
bool cmp(pair<long long,long long> X,pair<long long,long long> Y){
    if(X.first>Y.first)return false;
    else if(X.first==Y.first && X.second>Y.second)return false;
    return true;
}
bool cautBin(int st,int dr,long long X1,long long Y1){
    while(st<=dr){
        int mij=(st+dr)/2;
        if(ob[mij].first==X1 && ob[mij].second==Y1)return true;
        else if(ob[mij].first>X1)dr=mij-1;
        else if(ob[mij].first<X1)st=mij+1;
        else if(ob[mij].first==X1){
            if(ob[mij].second>Y1)dr=mij-1;
            else if(ob[mij].second<Y1)st=mij+1;
        }
    }
    return false;
}
int main()
{
    f>>N>>M;
    for(int i=1;i<=N;++i)
        f>>x>>y,ob.push_back(make_pair(x,y));
    sort(ob.begin(),ob.begin()+N,cmp);
    for(int o=1;o<=M;++o){
        f>>x>>y>>r;
        long long nr=0;
        for(int k=1;k<=r;++k)
            for(int var=0;var<8;++var)
                if(cautBin(0,N-1,x+r*dx[var],y+r*dy[var]) && abs(r*dx[var])+abs(r*dy[var])==r)
                    ++nr;
        g<<nr<<'\n';
    }
    return 0;
}