Comment

Westbrook: 2024-05-17 09:39:35
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int N = 10000;
struct Pos
{
	double x, y;
	double x_resct, y_resct;//存储该点形成的圆与x轴相交的两点
	bool operator<(const Pos &M)
	{
		return y_resct < M.y_resct;
	}
}pos[N];
int m;
bool cover[N];
void solve()
{
	int n, d;
	cin >> n >> d;
	for (int i = 0; i < n; i++)
	{
		cin >> pos[i].x >> pos[i].y;
		pos[i].x_resct = pos[i].x - sqrt(d * d - pos[i].y * pos[i].y);
		pos[i].y_resct = pos[i].x + sqrt(d * d - pos[i].y * pos[i].y);
	}
	sort(pos, pos + n);//对该点形成的圆与x轴右交点进行排序
	int ans = 0;
	double max_r;//存储当前x轴上最右端点的值
	for (int i = 0; i < n; i++)
	{
		if (cover[i] == true)//当前船只已被覆盖
		{
			continue;
		}
		else//当前船只未被覆盖
		{
			ans++;//添加一个基站
			cover[i] = true;//当前船只被覆盖
			max_r = pos[i].y_resct;
			for (int j = i; j < n; j++)//判断该基站能否覆盖之后的基站
			{
				if (pos[j].x_resct <= max_r&&cover[j]==false)
				{
					cover[j] = true;
				}
				else
				{
					if (pos[j].x_resct > max_r)
					{
						break;
					}
				}
			}
		}
	}
	cout << ans << endl;
}


int main()
{
	cin >> m;
	while (m--)
	{
		memset(cover, false, sizeof cover);
		solve();
	}
	return 0;
}直接把与x轴的左右交点存储下来即可，然后对右交点进行排序，不断枚举，时间复杂度O（n）