10pts求助
查看原帖
10pts求助
1066565
Zhang_xiangyou楼主2024/12/21 17:24
#include <bits/stdc++.h>
using namespace std;
int n,m,X,Y,P,R,t,flag,ans;
int l[250005],r[250005],p[250005];
bool vis[250005];
struct node
{
	int x,y,m,p,r;
	double dis;	
}a[250005];
queue<node> q;
double dis(int x,int y) 
{
	return sqrt((x-X)*(x-X)+(y-Y)*(y-Y));
}
bool cmp(node a,node b) 
{
	return a.m < b.m;	
}
bool cmp2(node a,node b) 
{
	return a.dis < b.dis;
}
int main()
{
	cin >> X >> Y >> P >> R >> n;
	q.push(node{X,Y,0,P,R});
	for (int i=1;i<=n;i++)
	{
		scanf("%d%d%d%d%d",&a[i].x,&a[i].y,&a[i].m,&a[i].p,&a[i].r);
		a[i].dis = dis(a[i].x,a[i].y);
	}
	sort(a+1,a+n+1,cmp);
	int s = sqrt(n);
	for (int i=1;i<=s;i++)
	{
		l[++t] = (i-1)*s+1;
		r[t] = i*s;
		sort(a+l[t],a+r[t]+1,cmp2);
	}
	if (r[t] != n)
	{
		l[++t] = s*s+1;
		r[t] = n;
		sort(a+l[t],a+r[t]+1,cmp2);
	}
	while (q.size())
	{
		flag = 0;
		node u = q.front();
		P = u.p;
		R = u.r;
//		printf("the new stone which is added: p=%d r=%d\n",P,R);
		q.pop();
		for (int i=1;flag==0&&i<=t;i++)
		{
			for (int j=l[i];j<=r[i];j++)
			{
				if (a[j].m > P)
				{
					flag = i;
					break;
				}
				if (a[j].dis <= R)
				{
//					printf("the new stone which is chose: x=%d y=%d p=%d r=%d dis=%.5lf\n",a[j].x,a[j].y,a[j].p,a[j].r,a[j].dis);
					ans++;
					q.push(a[j]);
					l[i] = j+1;
				}
			}
		}
		for (int i=l[flag];i<=r[flag];i++)
		{
			if ((a[i].m <= P && a[i].dis <= R) && vis[i] == 0)
			{
//				printf("the new stone which is chose: x=%d y=%d p=%d r=%d dis=%.5lf\n",a[i].x,a[i].y,a[i].p,a[i].r,a[i].dis);	
				vis[i] = 1;
				ans++;
				q.push(a[i]);
			}
		}
	}
	cout<<ans;
	return 0;
}
2024/12/21 17:24
加载中...