Problem E
Watering Grass
Input:standard input
Output:standard output
Time Limit:3 seconds
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
2
-1
转化为区间嵌套,用圆和矩形的边形成的弦区间,贪心求之,注意精度问题
#include <iostream>
#include <cstring>
#include <string>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstdlib>
using namespace std;
struct data{
double x,y;
}f[10010];
#define eps 1e-7
inline int ifcmp(double x){//精度
if (x > -eps) return 1;
else return -1;
}
bool cmp(data a,data b)
{
return a.x<b.x||(a.x==b.x&&a.y>b.y);
}
int main()
{
int n,l,w,i,j,k,a,b;
while(scanf("%d%d%d",&n,&l,&w)!=EOF)
{
for(i=0,j=0;i<n;i++)
{
scanf("%d%d",&a,&b);
if(2*b<w)
continue;
double tem;
tem=sqrt((double)b*b-(double)w*w/4.0);//半弦
f[j].x=a-tem;
f[j].y=a+tem;
j++;
}
sort(f,f+j,cmp);
int pre=0,pos,sum=0,max_j;
sum=1;
i=1;
max_j=0;
while(true)
{
bool flag=false;
while(ifcmp(f[pre].y-f[i].x)>0&&i<j)
{
flag=true;
if(ifcmp(f[i].y-f[max_j].y)>0)
max_j=i;
i++;
}
if(!flag||(i>j&&ifcmp(f[max_j].y-(double)l)<0))
{
sum=-1;
break;
}
pre=max_j;
sum++;
if(ifcmp(f[max_j].y-(double)l)>0)
break;
}
printf("%d\n",sum);
}
}
分享到:
相关推荐
Lazarus & Watering-hole attacks 该报告根据本文中共享的内容以及作者的其他发现提供了有关水坑攻击的概述。
太阳能自动洒水系统设计 MF6210无线收发模块代码。
浇水watering-pi是基于框架构建的聊天机器人。 它最初是由,并被配置为部署在以使您尽快启动并运行。 本自述文件旨在帮助您入门。 绝对会进行更新和改进,以谈论您自己的实例,如何使用和部署,他具有什么功能等等!...
浇水追踪器使用React Native的浇水追踪器应用程序
基于eclipse的java实现的数字水印技术
植物浇水系统 一个用于监控植物并远程浇水的应用程序
温室智能花浇水系统关于项目我们的团队致力于设计基于Raspberry Pi的温室智能花卉浇水系统。 该系统可以实时检测温室的环境参数和土壤湿度。 如果土壤湿度高于或低于阈值,Raspberry Pi将控制水管浇灌植物。...
基于proteus的自动浇花装置硬件电路图
watering_node 一个简单的基于arduino pro mini的浇水自动化系统,适用于一个工厂。 可以单独使用已编程的参数,但是它也是一个I2c从站,可以通过它设置参数并可以传输数据。 包括: 土壤水分传感器 DHT11 i2c从...
植物浇水和/或喂食系统。 该系统将由太阳能供电,并能够为小型植物系统提供微水。 最初将储存五加仑的水或营养液,供大约 4 个成年番茄植株使用五天。... https://sourceforge.net/p/watering-kit/wiki/Home/
理论 浇水的主要配方: (Eto x PF x SF x 0.62 ) / IE = Gallons of Water per day 在哪里: Eto :从获取PF :这是植物因素。 不同的植物需要不同的水量。... npm install watering 用法 确保首先更改c
Automated-Watering:带有rasperri pi的系统可自动进行水生植物
使用arduino的花园给水系统 这是一个使用Arduino为花园浇水的项目。 为此,我使用了一个电动阀来控制浇水,使用了一个传感器来测量温度和湿度,使用了LCD显示屏为用户编写信息,使用了两个按钮来修改浇水时间并打开...
通过remotexy应用程序平台使用wifi:什么是remotexy:是一个用于控制arduino,raspberry pi或任何其他开发板的平台。 它提供了图形界面,仅通过使用一些小部件或按钮即可控制和监视我们的项目。...
rose_watering_app 该应用程序提醒我的朋友,如果下雨不超过5天,请为玫瑰浇水。 该应用程序使用异步js通过GET方法获取天气api。 应用程序的最终目标是向我的朋友发送一封电子邮件,提醒他们浇玫瑰。 此时,该...
自动浇水 自己动手自己的自动浇水项目 1.物料清单 迷你水泵x 1 PVC管内径D = 6mm,外径D = 8mm 电动机驱动器DRV8833 ESP8266开发板D1 mini 电容式湿度传感器 行动电源DIY套件 18650电池x 1 ...
浇水 我的 Arduino-Raspberry-web.py REST 项目
在打开此页面 用作扩展 该存储库可以作为扩展添加到MakeCode中。 打开 ...搜索并导入 编辑这个专案 要在MakeCode中编辑此存储库。... 单击导入,然后单击导入URL ...此图显示了master中最后一次提交的块代码。...
地穴兰花喷壶 该项目包含一个安全帽脚本,该脚本允许CryptOrchid的所有者通过调用以太坊区块链上CryptOrchidsERC721智能合约上的water函数来浇灌植物。 该脚本的目的是防御性的,旨在仅在需要浇水时才浇水。...
自浇水系统作者:斯科特·特林布尔概念创建一个监视植物土壤湿度的系统。 该系统将具有一个水箱,当工厂需要水时,该水箱将启动泵并为工厂浇水。 水箱将位于花盆下方,以便多余的水排回到水箱中。...