链接:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=113&page=show_problem&problem=1323
原题:
nsprinklers are installed in a horizontal strip of grasslmeters long andwmeters wide. Each sprinkler is installed at the horizontal center line of the strip. For each sprinkler we are given its position as the distance from
the left end of the center line and its radius of operation.
What is the minimum number of sprinklers to turn on in order to water the entire strip of grass?
Input
Input consists of a number of cases. The first line for each case contains integer numbersn,landwwithn<= 10000. The nextnlines contain two integers giving the position of a sprinkler and its radius of
operation. (The picture above illustrates the first case from the sample input.)
Output
For each test case output the minimum number of sprinklers needed to water the entire strip of grass. If it is impossible to water the entire strip output -1.
Sample input
8 20 2
5 3
4 1
1 2
7 2
10 2
13 3
16 2
19 4
3 10 1
3 5
9 3
6 1
3 10 1
5 3
1 1
9 1
Sample output
6
题目大意:
有一块草坪,长为l,宽为w,在它的水平中心线上有n个位置可以安装喷水装置,各个位置上的喷水装置的覆盖范围为以它们自己的半径ri为圆。求出最少需要的喷水装置个数。
分析与总结:
这题的关键在于转化
根据这图可以看出,一个喷水装置的有效覆盖范围就是圆中间的那个矩形。所以,在输入的同时,进行预处理,转换成矩形左边的坐标和右边的坐标。 这样,其实就转换成了经典的区间覆盖问题。
代码:
/*
* UVa: 10382 - Watering Grass
* 贪心:最小覆盖
* Result: Accept
* Time: 0.016s
* Author: D_Double
*/
#include<iostream>
#include<cmath>
#include<cstdio>
#include<algorithm>
#define MAXN 10005
using namespace std;
int n,nIndex;
double l, w;
struct Node{
double left;
double right;
friend bool operator < (const Node&a,const Node&b){
return a.left < b.left;
}
}arr[MAXN];
int main(){
double p,r;
while(scanf("%d%lf%lf",&n,&l,&w)!=EOF){
nIndex=0;
for(int i=0; i<n; ++i){
scanf("%lf%lf",&p,&r);
if(w/2>=r)
continue; //直径小于宽度的不考虑
double t=sqrt(r*r-w*w/4.0);
arr[nIndex].left=p-t;
arr[nIndex].right=p+t;
++nIndex;
}
sort(arr,arr+nIndex);
int cnt=0;
double left=0, right=0;
bool flag=false;
if(arr[0].left <= 0 ){
int i=0;
while(i < nIndex){
int j=i;
while(j<nIndex && left>=arr[j].left){
if(arr[j].right > right)
right=arr[j].right;
++j;
}
if(j==i) break; // 如果上面的循环体没有执行,说明之后都没有满足的了
++cnt;
left=right;
i=j;
if(left>=l){
flag=true;
break;
}
}
}
if(flag) printf("%d\n", cnt);
else printf("-1\n");
}
return 0;
}
—— 生命的意义,在于赋予它意义。
分享到:
相关推荐
温室智能花浇水系统关于项目我们的团队致力于设计基于Raspberry Pi的温室智能花卉浇水系统。 该系统可以实时检测温室的环境参数和土壤湿度。 如果土壤湿度高于或低于阈值,Raspberry Pi将控制水管浇灌植物。...
植物浇水系统 一个用于监控植物并远程浇水的应用程序
Automated-Watering:带有rasperri pi的系统可自动进行水生植物
通过remotexy应用程序平台使用wifi:什么是remotexy:是一个用于控制arduino,raspberry pi或任何其他开发板的平台。 它提供了图形界面,仅通过使用一些小部件或按钮即可控制和监视我们的项目。...
使用arduino的花园给水系统 这是一个使用Arduino为花园浇水的项目。 为此,我使用了一个电动阀来控制浇水,使用了一个传感器来测量温度和湿度,使用了LCD显示屏为用户编写信息,使用了两个按钮来修改浇水时间并打开...
地穴兰花喷壶 该项目包含一个安全帽脚本,该脚本允许CryptOrchid的所有者通过调用以太坊区块链上CryptOrchidsERC721智能合约上的water函数来浇灌植物。 该脚本的目的是防御性的,旨在仅在需要浇水时才浇水。...
自动浇水 自己动手自己的自动浇水项目 1.物料清单 迷你水泵x 1 PVC管内径D = 6mm,外径D = 8mm 电动机驱动器DRV8833 ESP8266开发板D1 mini 电容式湿度传感器 行动电源DIY套件 18650电池x 1 ...
自浇水系统作者:斯科特·特林布尔概念创建一个监视植物土壤湿度的系统。 该系统将具有一个水箱,当工厂需要水时,该水箱将启动泵并为工厂浇水。 水箱将位于花盆下方,以便多余的水排回到水箱中。...
在打开此页面 用作扩展 该存储库可以作为扩展添加到MakeCode中。 打开 ...搜索并导入 编辑这个专案 要在MakeCode中编辑此存储库。... 单击导入,然后单击导入URL ...此图显示了master中最后一次提交的块代码。...
远程浇水系统APP远程监测,控制系统(云服务器,CC3200)文件说明FlowerManager:安卓应用程序代码。 CC3200的一部分:CC3200相关代码。 SpringBoot的一部分:主要后台代码部分。
Lazarus & Watering-hole attacks 该报告根据本文中共享的内容以及作者的其他发现提供了有关水坑攻击的概述。
浇水watering-pi是基于框架构建的聊天机器人。 它最初是由,并被配置为部署在以使您尽快启动并运行。 本自述文件旨在帮助您入门。 绝对会进行更新和改进,以谈论您自己的实例,如何使用和部署,他具有什么功能等等!...
太阳能自动洒水系统设计 MF6210无线收发模块代码。
岗楼 Watchtower 是一种服务,用于在(几乎)实时的许多不同类型的设备之间轻松交互。...* All your flower-watering Arduinos register and joins a channel * Your Macbook joins the same channel *
浇水追踪器使用React Native的浇水追踪器应用程序
植物浇水和/或喂食系统。 该系统将由太阳能供电,并能够为小型植物系统提供微水。 最初将储存五加仑的水或营养液,供大约 4 个成年番茄植株使用五天。... https://sourceforge.net/p/watering-kit/wiki/Home/
基于eclipse的java实现的数字水印技术
浇水 我的 Arduino-Raspberry-web.py REST 项目
watering_node 一个简单的基于arduino pro mini的浇水自动化系统,适用于一个工厂。 可以单独使用已编程的参数,但是它也是一个I2c从站,可以通过它设置参数并可以传输数据。 包括: 土壤水分传感器 DHT11 i2c从...
基于proteus的自动浇花装置硬件电路图