题目链接:http://poj.org/problem?id=1328
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 52768 | Accepted: 11867 |
Description
Input
Output
Sample Input
3 2 1 2 -3 1 2 1 1 2 0 2 0 0
Sample Output
Case 1: 2 Case 2: 1
Source
源代码:
#include <iostream> #include <cmath> #include <string.h> #include <algorithm> #include <cstdio> #include <vector> #include <utility> using namespace std; const int maxn = 1000 + 5; int main() { int n, k = 1; double d; while (scanf("%d%lf", &n, &d) && (n != 0 || d != 0)) { vector<pair<double, double> > st; bool vis[maxn]; memset(vis, false, sizeof(vis)); double x, y, l, r; bool flag = false; for (int i = 0; i < n; ++i) { scanf("%lf%lf", &x, &y); if (y > d) flag = true; if (!flag) { l = x - sqrt(d * d - y * y); r = x + sqrt(d * d - y * y); st.push_back(make_pair(r, l)); } } if (flag) { printf("Case %d: -1\n", k++); continue; } int count = 0; sort(st.begin(), st.end()); memset(vis, false, sizeof(vis)); for (int i = 0; i < st.size(); ++i) { if (vis[i]) continue; ++count; r = st[i].first; vis[i] = true; for (int j = i + 1; j < st.size(); ++j) if (st[j].second <= r) vis[j] = true; } printf("Case %d: %d\n", k++, count); } }
对于每一个岛屿,在x轴上都有一个雷达可覆盖其的区间,求最少的雷达,使所有岛屿对应的区间上至少有一个雷达。
将这些区间按照右端点从小到大排序。选择在右端点建设雷达,进行刷选去除。比如,第一个区间为[l, r],则剩下区间中左端点小于r的都去掉。
如此类推……
Poj 1328 Radar Installation 贪心,布布扣,bubuko.com
Poj 1328 Radar Installation 贪心
原文:http://blog.csdn.net/u010826976/article/details/38709251