题意:地图的x轴的上方为海,下方为陆地,海中有n个小岛,坐标为(isl[i].x,isl[i].y)。有一种雷达,能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的,也就是x轴上的。
思路:贪心,从左到右建立雷达,要尽量多地覆盖岛屿。以岛屿为圆心,以d为半径画圆,如果画出的圆与x轴没有交点,则不能实现。存在交点的话,计算出第i个岛屿与x轴的交点坐标保存在结构体数组rad[i].sta与rad[i].end中。对结构体数组排序,按照rad[i].end进行升序排列,然后一次从左到右找雷达。对于rad[i].end为当前最右边的左坐标,对于下一个岛屿,如果rad[j].sta<ran[i].end,则不需要建立新的雷达,需要更新下一个岛屿。否则需要建立新的雷达。具体代码如下:
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
const int Max = 1005;
struct
{
int x, y;
}isl[Max]; // 小岛的数据。
struct data
{
float sta, end;
}rad[Max]; // 小岛所对应雷达的数据。
bool cmp(data a, data b)
{
if(a.end < b.end)
return true;
else
return false;
}
int main()
{
int n, d, t = 1;
while(cin >> n >> d && n != 0)
{
int i, j, max_y = 0;
for(i = 0; i < n; i ++)
{
cin >> isl[i].x >> isl[i].y;
if(isl[i].y > max_y)
max_y = isl[i].y;
}
getchar();
getchar(); // PE了两次。
cout << "Case " << t ++ << ": ";
if(max_y > d || d < 0)
{
cout << -1 << endl;
continue;
}
float len;
for(i = 0; i < n; i ++)
{ // 求出小岛所对应雷达的可能覆盖范围。
len = sqrt(1.0 * d * d - isl[i].y * isl[i].y);
rad[i].sta = isl[i].x - len;
rad[i].end = isl[i].x + len;
}
sort(rad, rad + n, cmp); // 根据rad的end值进行排序。
int ans = 0;
bool vis[Max];
memset(vis, false, sizeof(vis));
for(i = 0; i < n; i ++)
{ // 类似的活动选择。
if(!vis[i])
{
vis[i] = true;
for(j = 0; j < n; j ++)
if(!vis[j] && rad[j].sta <= rad[i].end)
vis[j] = true;
ans ++;
}
}
cout << ans << endl;
}
return 0;
}
分享到:
相关推荐
poj1087贪心算法实验报告 poj1087贪心算法实验报告
(poj1753,poj2965)(2)贪心(poj1328,poj2109,poj2586)(3)递归和分治法.(4)递推.(5)构造法.(poj3295)……中级有:(1)C++的标准模版库的应用. (poj3096,poj3007)(2)较为复杂的模拟题的训练(poj3393,poj1472,poj3371,...
用贪心算法解决POJ 1065的木棍处理问题
(2)贪心(poj1328,poj2109,poj2586) (3)递归和分治法. (4)递推. (5)构造法.(poj3295) (6)模拟法.(poj1068,poj2632,poj1573,poj2993,poj2996) 二.图算法: (1)图的深度优先遍历和广度优先遍历. (2)最短...
一.基本算法:枚举. (poj1753,poj2965)贪心(poj1328,poj2109,poj2586)递归和分治法
NULL 博文链接:https://128kj.iteye.com/blog/1759266
NULL 博文链接:https://128kj.iteye.com/blog/1686093
第 17 题:poj 1042 钓鱼John starts at lake 1, but he can finish at any lake he wants.
史上最全poj题目分类及原题 包括:基本算法:贪心、递归、递推、枚举;基本数据结构,链表、栈;动态规划;搜索;高级数据结构:二叉搜索树、线段树、树状数组;数学:数论
poj题目分类 简单题 搜索题 模拟题 动态规划 计算几何 递推 数学题 图论 数据结构 贪心 构造 枚举 特殊问题特殊对待 博弈 适合学算法的人进行专项练习
poj题目分类,适合acmer学习研究 主流算法: 1.搜索 //回溯 2.DP(动态规划) 3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7....
Algorithm-Java Algorithms + Data Structures = Programs....最短路径(dijkstra,bellman-ford,floyd,heap+dijkstra)(,,poj1062,poj2253,poj1125,poj2240) 最小生成树(prim,kruskal)(p
AlgoHub囊括了 POJ, ZOJ, leetcode, HackerRank 等网站的经典题目(一些质量不高的题目则忽略),且 AlgoHub有非常简单的加题系统,用户不需要写一行代码即可自己添加题目,所以AlgoHub的题库还在飞速增长中。...
leetcode题库 编程练习 御航智能算法组编程练习专用。 说明 本题库将汇集POJ、HDOJ、LeetCode等主流程序在线评测系统的题目,列出题目类别、描述、链接,...贪心算法—— 第3节 双指针—— 回溯算法—— 进阶篇 高阶篇
动态规划 01背包问题 POJ3624可以AC
3.贪心 4.图论 //Dijkstra、最小生成树、网络流 5.数论 //解模线性方程 6.计算几何 //凸壳、同等安置矩形的并的面积与周长 7.组合数学 //Polya 定理 8.模拟 9.数据结构 //并查集、堆 10.博弈论 1、 排序 2、 搜索、...
4.3 成为图论大师之路 4.3.1 强连通分量分解 4.3.2 2-SAT 4.3.3 LCA 4.4 常用技巧精选(二) 4.4.1 栈的运用 4.4.2 双端队列的运用 4.4.3 倍增法 4.5 开动脑筋智慧搜索 4.5.1 剪枝 4.5.2 A*与IDA* 4.6 划分、解决、...
#POJ 题集 数论 欧几里得/拓展欧几里得算法 1006 1061 搜索 普通搜索 1062, 1088, 2386 剪枝优化 1011 动态规划 背包 1014 高精度 加减乘除 1001 巧妙处理 思维处理 1852 模拟 1017 简单题 水题 1004 1007 1008 枚举...