Pagini recente » Cod sursa (job #1655907) | Cod sursa (job #388875) | Cod sursa (job #2285342) | Cod sursa (job #1684593) | Cod sursa (job #2561729)
#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;
}