Cod sursa(job #2561729)

Utilizator 12222Fendt 1000 Vario 12222 Data 29 februarie 2020 09:38:59
Problema Ubuntzei Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.11 kb
#include <bits/stdc++.h>

using namespace std;

const int Emax = 4e5 + 2;
const int Mmax = 1e5 + 2;
const int Nmax = 2e5 + 2;
const int oo = 2e9;

ofstream fout("nuke.out");

class InputReader {
private:
	static const int BUFF_SIZE = 100000;
	FILE *fin;
	int bp;
	char buff[BUFF_SIZE];
	inline void nxt() {
		if (++bp == BUFF_SIZE) {
			fread(buff, sizeof(char), BUFF_SIZE, fin);
			bp = 0;
		}
	}
public:
	InputReader(const char *file_name) {
		fin = fopen(file_name, "r");
		bp = BUFF_SIZE - 1;
	}
	void close() {
		fclose(fin);
	}
	InputReader& operator >> (int &num) {
		num = 0;
		while (isdigit(buff[bp]) == 0 && buff[bp] != '-')
			nxt();
		int semn = 1;
		if (buff[bp] == '-')
		{
			semn = -1;
			nxt();
		}
		while (isdigit(buff[bp])) {
			num = num * 10 + (buff[bp] - '0')*semn;
			nxt();
		}
		return *this;
	}
} fin("nuke.in");

int n, m;
int sol[Mmax];
tuple <int, int, int> cerc[Mmax];
pair <int, int> pct[Nmax];
set <pair <int, int> >s;

struct Event
{
    int type;
    int x, pos;

    bool operator < (const Event &e) const
    {
        if(x == e.x) return type < e.type;
        return x < e.x;
    }

}e[Emax];

inline bool get_dist(int x1, int y1, int x2, int y2, int r)
{
    return (1LL * (x1 - x2) * (x1 - x2) + 1LL * (y1 - y2) * (y1 - y2) <= 1LL * r * r);
}

int main()
{
    fin >> n >> m;

    int x, y, r;
    for(int i = 1; i <= n; i++)
    {
        fin >> x >> y;
        pct[i] = {x, y};
        e[i].type = 0;
        e[i].x = x;
        e[i].pos = i;
    }

    int lg = n;
    for(int i = 1; i <= m; i++)
    {
        fin >> x >> y >> r;
        cerc[i] = make_tuple(x, y, r);

        lg++;
        e[lg].type = -1;
        e[lg].x = x - r;
        e[lg].pos = i;
        lg++;
        e[lg].type = 1;
        e[lg].x = x + r;
        e[lg].pos = i;
    }

    sort(e + 1, e + lg + 1);

    int p;
    set < pair <int, int> >::iterator it;

    for(int i = 1; i <= lg; i++)
    {
        if(e[i].type == -1) s.insert({get<1>(cerc[e[i].pos]), e[i].pos});
        else if(e[i].type == 1) s.erase({get<1>(cerc[e[i].pos]), e[i].pos});
        else {

            if(s.empty())
                continue;

            it = s.lower_bound({pct[e[i].pos].second, 0});

            if(it != s.end())
            {
                y = (*it).first;
                p = (*it).second;
                r = get<2>(cerc[p]);
                x = get<0>(cerc[p]);
                if(get_dist(e[i].x, pct[e[i].pos].second, x, y, r))
                {
                    sol[p]++;
                    continue;
                }
            }

            if(it != s.begin())
            {
                it = prev(it);
                y = (*it).first;
                p = (*it).second;
                r = get<2>(cerc[p]);
                x = get<0>(cerc[p]);
                if(get_dist(e[i].x, pct[e[i].pos].second, x, y, r))
                    sol[p]++;
            }

        }
    }

    for(int i = 1; i <= m; i++)
        fout << sol[i] << "\n";

    fin.close();
    fout.close();
    return 0;
}