文章
25
粉丝
0
获赞
0
访问
68517
分块+bfs:
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int N = (int)2e6;
const int w = 500;//块长度
typedef long long ll;
ll xx, yy, l[N], r[N], num, n, x, y, D[N], v[N];//D[N]记录每一块距离源点最大的d
struct node{
ll m, r, d, p;
}a[N];
bool cmp_d(node a, node b){
return a.d < b.d;
}
bool cmp_m(node a, node b){
return a.m < b.m;
}
ll dfs(){
queue<ll >q;
q.push(0);
ll ans = 1;
while (q.size()){
ll t = q.front();
q.pop();
for (int i = 1; i <= num; i++){//对于每一个块进行更新
if (D[i]>a[t].r){//两边暴力
for (ll j = l[i]; j <= r[i]; j++){
if (!v[j] && a[j].d <= a[t].r&&a[j].m <= a[t].p){
q.push(j);
ans++;
v[j] = 1;
}
}
break;//已经是最右边的块了,直接break
}
while (l[i] <= r[i] && a[l[i]].m <= a[t].p){//距离已经在磁力半径之内,判断质量
if (!v[l[i]]){
q.push(l[i]);
ans++;
}
l[i]++;
}
}
}
return ans;
}
int main(){
cin >> xx >> yy >> a[0].p >> a[0].r >> n;
a[0].r *= a[0].r;
for (int i = 1; i <= n; i++){
cin >> x >> y >> a[i].m >> a[i].p >> a[i].r;
a[i].r *= a[i].r;
a[i].d = (x - xx)*(x - xx) + (y - yy)*(y - yy);
}
//按距离d进行排序
sort(a+1, a + n+1, cmp_d);
//分组
for (ll i = 1; i <= n; i+=w){
l[++num] = i;
r[num] = min(n, i + w - 1);
D[num] = a[r[num]].d;
sort(a + l[num], a + r[num] + 1, cmp_m);//快内按照质量进行排序
}
ll ans=dfs();
cout << ans-1 << endl;
return 0;
}
登录后发布评论
暂无评论,来抢沙发