Poj 1328 / OpenJudge 1328 Radar Installation
1.Link:
http://poj.org/problem?id=1328
http://bailian.openjudge.cn/practice/1328/
2.Content:
Radar Installation
Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 52833 Accepted: 11891 Description
Assume the coasting is an infinite straight line. Land is in one side of coasting, sea in the other. Each small island is a point locating in the sea side. And any radar installation, locating on the coasting, can only cover d distance, so an island in the sea can be covered by a radius installation, if the distance between them is at most d.We use Cartesian coordinate system, defining the coasting is the
x-axis. The sea side is above x-axis, and the land side below. Given the
position of each island in the sea, and given the distance of the
coverage of the radar installation, your task is to write a program to
find the minimal number of radar installations to cover all the islands.
Note that the position of an island is represented by its x-y
coordinates.
Figure A Sample Input of Radar Installations
Input
The
input consists of several test cases. The first line of each case
contains two integers n (1<=n<=1000) and d, where n is the number
of islands in the sea and d is the distance of coverage of the radar
installation. This is followed by n lines each containing two integers
representing the coordinate of the position of each island. Then a blank
line follows to separate the cases.The input is terminated by a line containing pair of zeros
Output
For
each test case output one line consisting of the test case number
followed by the minimal number of radar installations needed. "-1"
installation means no solution for that case.Sample Input
3 2
1 2
-3 1
2 1 1 2
0 2 0 0Sample Output
Case 1: 2
Case 2: 1Source
3.Method:
(1)求出每个岛能够安装灯塔的区域,用结构体表示Lines
(2)根据最右快排,这里要尤其注意double类型的compare怎么写
(3)贪心算法求最小灯塔数量
4.Code:
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>using namespace std;
struct LINE
{
double l;
double r;
};int cmp(const void *a,const void *b)
{
LINE line1 = *((LINE *)a);
LINE line2 = *((LINE *)b);
/*if(line1.r == line2.r)
{
if(line1.l == line2.l) return 0;
return line1.l > line2.l ? 1 : -1;
}
else return line1.r > line2.r ? 1 : -1;*/
if(line1.r == line2.r) return 0;
else return line1.r > line2.r ? 1 : -1;
}int main()
{
//freopen("D://input.txt", "r", stdin);int i;
int n,d;
int count = 1;
int x,y;
int flag;
double ins;
cin >> n >> d;
while(n!= 0 || d != 0)
{LINE *lines = new LINE[n];
flag = 1;
for(i = 0; i < n; ++i)
{
cin>>x>>y;
if(d < y) flag = 0;
else
{
ins = sqrt(d * d - y * y);
lines[i].l = x - ins;
lines[i].r = x + ins;
}
}if(flag == 0) cout<<"Case "<< (count++) <<": -1"<<endl;
else
{
qsort(lines,n,sizeof(LINE),cmp);
/*for(i = 0; i < n; ++i)
{
cout << lines[i].l << " " << lines[i].r << endl;
}*/
int num = 1;
double max_r = lines[0].r;
for(i = 1; i < n; ++i)
{
if(max_r < lines[i].l)
{
num++;
max_r = lines[i].r;
}
}
cout << "Case " << (count++) << ": " << num <<endl;
}
delete [] lines;
cin >> n >> d;
}//fclose(stdin);
return 0;
}
5:Reference:
http://blog.sina.com.cn/s/blog_48f85e1d0100nslz.html
最新文章
- Java Web之会话管理一: 使用Cookie进行会话管理
- Google Tensorflow 源码编译(三):tensorflow<;v0.5.0>;
- OpenSource.organization-in-github
- Microsoft Visual Studio 2010 已安装的模板 没有 “ADO.NET实体数据模型”
- python排序算法的实现-插入
- Java架构师之路:JAVA程序员必看的15本书
- openfire开发
- phpcms v9和discuz X3.1实现同步登陆退出论坛(已实现)
- IBM X3650 服务器更换内存的过程记录
- 【转】ubuntu下putty的复制粘贴 -- 不错
- CLLocation
- Redis在win7上的安装与可视化应用
- Nmap绕过防火墙&;脚本的使用
- FFmpeg与libx264接口源代码简单分析
- dat.gui stats.js 通用参数配置及图像统计工具
- .net core2 单元测试
- spring boot 项目启动无任何反应
- Kotlin入门(6)条件分支的实现
- 手把手教你封装 Vue 组件并使用 NPM 发布
- leetcode-876 Middle of the Linked List
热门文章
- delphi 判断是否出现滚动条
- PHP获取用户真实 IP , 淘宝IP接口获得ip地理位置(转)
- focusky 购买指南
- query插件之ajaxForm ajaxSubmit的理解用法
- Cross Site Request Forgery (CSRF)--spring security -转
- Qt focusoutevent 不响应的解决方法
- C# WinForm 中ComboBox数据绑定的问题 (转)
- Xquartz远程访问linux
- linux-cat/less/more/tail
- oracle 10g升级到11g