B

.

【

例

题

2

】

雷

达

装

置

B. 【例题2】雷达装置

B.【例题2】雷达装置

题目解析

求最少所需的雷达数,考虑贪心算法.

以这张图为例.以一个城市为中心,作一个半径为

d的圆.而这个圆与

x轴的左交点

l到右交点

r的区间

[

]

[l,r]

[l,r]内的说有点放置雷达都可以至少笼罩住这个城市.

因为是贪心思想,那么就尽量是最多区间的点,并且优先最右端.

Code

#include <bits/stdc++.h>

#define db double

using namespace std;

struct abc{

	db x, y;

}a[1005];

db h[10005];

int n, d, ans;

bool cmp(abc a, abc b)

{

	return a.y < b.y;

}

int main()

{

	scanf ("%d%d", &n, &d);

	for (int i = 1; i <= n; ++ i)

	{

		int t1, t2;

		scanf ("%d%d", &t1, &t2);

		db er = sqrt (d * d - t2 * t2);

		if(t2 > d)

		{

			ans = -1;

			break;

		}

		a[i].x = t1 - er;

		a[i].y = t1 + er;

	}

	if (ans < 0)

	{

		printf ("-1");

		return 0;

	}

	sort (a + 1, a + n + 1, cmp);

	h[ ++ ans] = a[1].y;

	for (int i = 2; i <= n; ++ i)

	{

		if (h[ans] < a[i].x)

			h[ ++ ans] = a[i].y;

	}

	printf ("%d", ans);

	return 0;

}

巴特西

B. 【例题2】雷达装置

B

.

【

例

题

2

】

雷

达

装

置

B. 【例题2】雷达装置

B.【例题2】雷达装置

题目解析

Code

最新文章

热门文章

巴特西

B. 【例题2】雷达装置

B . 【 例 题 2 】 雷 达 装 置 B. 【例题2】雷达装置 B.【例题2】雷达装置

题目解析

Code

最新文章

热门文章

B

.

【

例

题

2

】

雷

达

装

置

B. 【例题2】雷达装置

B.【例题2】雷达装置