POJ1328 贪心

2017年3月18日 | ljfcnyali

题目大意

地图的x轴的上方为海，下方为陆地，海中有n个小岛，坐标为(isl[i].x,isl[i].y)。有一种雷达，能探测到的范围为以d为半径的圆。问海岸线上至少造多少雷达可以把所有的小岛都包含在内。注意雷达是建在海岸线上的，也就是x轴上的。

Sample Input

3 2
1 2
- 
2 1

1 2
0 2

0 0
           

Sample Output

Case : 
Case : 
           

题目分析

使用贪心，从左往右建立雷达，要尽可能多的覆盖岛屿。

AC代码

/*************************************************************************
    > File Name: POJ1328.cpp
    > Author: ljf-cnyali
    > Mail: [email protected] 
    > Created Time: 2017/3/18 13:34:16
 ************************************************************************/

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>

using namespace std;

#define REP(i, a, b) for(int i = (a), _end_ = (b);i <= _end_; ++ i)
#define mem(a) memset((a), 0, sizeof(a))
#define str(a) strlen(a)

const int maxn = ;

struct Island {
    int x, y;
} isl[maxn];

struct node {
    float sta, end;
} red[maxn];

bool cmp(node x, node y) {
    return x.end < y.end;
}

int main() {
    int n, d, t = ;
    while(cin >> n >> d && n != ) {
        cout << "Case " << ++ t << ": ";
        int max_isl = ;
        REP(i, , n - ) {
            scanf("%d%d", &isl[i].x, &isl[i].y);
            max_isl = max(max_isl, isl[i].y);
        }
        if(max_isl > d || d < ) {
            cout << "-1" << endl;
            continue;
        }
        float len;
        REP(i, , n - ) {
            len = sqrt( * d * d - isl[i].y * isl[i].y);
            red[i].sta = isl[i].x - len;
            red[i].end = isl[i].x + len;
        }
        sort(red, red + n, cmp);
        int ans = ;
        bool vis[maxn];
        mem(vis);
        REP(i, , n - ) 
            if(!vis[i]) {
                vis[i] = true;  
                REP(j, , n - )
                    if(!vis[j] && red[j].sta <= red[i].end)
                        vis[j] = true;
                ++ ans;
            }
        printf("%d\n", ans);
    }
    return ;
}
           

本文转自：http://ljf-cnyali.cn/index.php/archives/66