UVA10382 Watering Grass

题目描述

长 \(L\) 米，宽 \(W\) 米的草坪里装有 \(n\) 个浇灌喷头。每个喷头都装在草坪中心线上（离两边各 \(\dfrac W 2\) 米）。我们知道每个喷头的位置（离草坪中心线左端的距离，即圆心坐标 \(x\)），以及它能覆盖到的浇灌范围，即半径 \(r\)。

请问：如果要同时浇灌整块草坪，最少需要打开多少个喷头？如果无解请输出 \(-1\)。

大体思路

代码

#include 
using namespace std;
#define rep(ii,aa,bb) for(re int ii = aa; ii <= bb; ii++)
#define Rep(ii,aa,bb) for(re int ii = aa; ii >= bb; ii--)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef pair PII;
const int maxn = 2e4 + 5;
const db eps = 1e-8;
namespace IO_ReadWrite {
	#define re register
	#define gg (p1 == p2 && (p2 = (p1 = _buf) + fread(_buf, 1, 1<<21, stdin), p1 == p2) ? EOF :*p1++)
	char _buf[1<<21], *p1 = _buf, *p2 = _buf;
	template 
	inline void read(T &x){
		x = 0; re T f=1; re char c = gg;
		while(c > 57 || c < 48){if(c == '-') f = -1;c = gg;}
		while(c >= 48 &&c <= 57){x = (x<<1) + (x<<3) + (c^48);c = gg;}
		x *= f;return;
	}
	inline void ReadChar(char &c){
		c = gg;
		while(!isalpha(c)) c = gg;
	}
	template 
	inline void write(T x){
		if(x < 0) putchar('-'), x = -x;
		if(x > 9) write(x/10);
		putchar('0' + x % 10);
	}
	template 
	inline void writeln(T x){write(x); putchar('\n');}
}
using namespace IO_ReadWrite;
ll n, tot;
db L, W;
struct Segment{ 
	db l, r;
	bool operator <(const Segment &x)const{
		return l < x.l;
	}
} a[maxn];
int main () {
//	int T; scanf("%d", &T);
	while(cin >> n >> L >> W) {
		tot = 0;
		rep(i, 1, n) {
			db x, r;
			cin >> x >> r;
			if(r * 2 <= W) continue;
			db _l = x - sqrt(r * r * 1.0 - W * W * 1.0 / 4.0);
			db _r = x + sqrt(r * r * 1.0 - W * W * 1.0 / 4.0);;
			a[++tot] = {_l, _r};
		}
		sort(a + 1, a + tot + 1);
		int ans = 0, i = 0; 
		db s = 0, ed = L * 1.0;
		while(s < L) {
			db mx = s;
			while(i < tot && a[i + 1].l <= s) {
				i ++;
				mx = max(mx, a[i].r);
			}
			ans ++;
			if(mx <= s && mx < ed) {
				ans = -1;
				break;
			}
			s = mx;
		}
		writeln(ans);
	}
	
	return 0;
}