生活随笔
收集整理的這篇文章主要介紹了
Watering Grass UVA - 10382 贪心
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
問題
https://vjudge.net/problem/UVA-10382
分析
將一個點的覆蓋范圍看作是一個長方形，舍棄弓形區域，變成區間覆蓋問題，用貪心法
注意：bb-ww/4有可能小于0，要篩出
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <map>
#include <string>
#include <vector>
#include <algorithm>
using namespace std
;
typedef long long LL
;
const int maxn
=10000+5;
const double eps
=1e-6;
struct spr
{double L
,R
;bool operator < (const spr
&rhs
) const {return L
<rhs
.L
;}
}sprs
[maxn
];
int n
,kase
=0,cnt
;
double l
,w
,a
,b
;
int main(void){while(scanf("%d%lf%lf",&n
,&l
,&w
)==3){cnt
=0;for(int i
=0;i
<n
;++i
){scanf("%lf%lf",&a
,&b
);if(b
<=w
/2+eps
) continue;double t
=sqrt(b
*b
-w
*w
/4);sprs
[cnt
].L
=a
-t
;sprs
[cnt
].R
=a
+t
;++cnt
;}sort(sprs
,sprs
+cnt
);int ans
=0,i
=0;double right
=0,maxr
=0;while(true){for(;i
<cnt
;++i
){if(sprs
[i
].L
<right
+eps
){maxr
=max(maxr
,sprs
[i
].R
);}else break;}if(maxr
-right
>eps
) {++ans
;right
=maxr
;}else break;if(right
>l
-eps
) break;}if(right
>l
-eps
) printf("%d\n",ans
);else printf("-1\n");}return 0;
}
總結
以上是生活随笔為你收集整理的Watering Grass UVA - 10382 贪心的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
