首页 > 代码库 > Uva 10382 (区间覆盖) Watering Grass

Uva 10382 (区间覆盖) Watering Grass

2024-07-20 14:57:46   224人阅读

和 Uva 10020几乎是一样的，不过这里要把圆形区域转化为能够覆盖的长条形区域(一个小小的勾股定理)

学习一下别人的代码，练习使用STL的vector容器

这里有个小技巧，用一个微小量EPS来弥补浮点运算中的误差

 

 1 //#define LOCAL 2 #include <vector> 3 #include <cstdio> 4 #include <cmath> 5 #include <algorithm> 6 #include <functional> 7 using namespace std; 8  9 const int MAXN = 10240;10 const double EPS = 1e-11;11 12 struct Range13 {14     double a, b;15     inline bool operator< (const Range& rhs) const16     {17         return a < rhs.a || (a == rhs.a && b < rhs.b);18     }19 };20 21 int main(void)22 {23     #ifdef LOCAL24         freopen("10382in.txt", "r", stdin);25     #endif26 27     int n, l, w;28     double lenth, width;29     vector<Range> ranges;30     ranges.reserve(MAXN);//reserve()函数提前设定容量大小，避免多次容量扩充操作导致效率低下31 32     while(scanf("%d%d%d", &n, &l, &w) == 3)33     {34         lenth = (double)l;35         width = w / 2.0;36         ranges.clear();37 38         for(int i = 0; i < n; ++i)39         {40             int position, radius;41             double xw;42             Range range;43 44             scanf("%d%d", &position, &radius);45             if(radius * 2 <= w)    continue;46             xw = sqrt((double)radius * radius - width * width);47 48             range.a = position - xw;49             if(range.a > lenth + EPS)    continue;50             else if(range.a - EPS < 0.0)    range.a = 0.0;51             range.b = position + xw;52             ranges.push_back(range);53         }54 55         sort(ranges.begin(), ranges.end());56 57         int minCover = 0;58         double start = 0.0, end = 0.0;59         for(vector<Range>::iterator pr = ranges.begin(); pr != ranges.end(); )60         {61             start = end;62             if(pr->a > start + EPS)63             {64                 minCover = -1;65                 break;66             }67             ++minCover;68             while(pr != ranges.end() && pr->a <= start)69             {70                 if(pr->b > end + EPS)    end = pr->b;71                 ++pr;72             }73             if(end > lenth + EPS)74                 break;75         }76         if(end + EPS < lenth)    minCover = -1;77         printf("%d\n", minCover);78     }79     return 0;80 }
代码君

 

Uva 10382 (区间覆盖) Watering Grass


联系
我们