首页 > 其他 > 详细

落谷p1325雷达安装[计算几何]

时间:2019-11-25 22:54:06      阅读:82      评论:0      收藏:0      [点我收藏+]

传送门

//p1325雷达安装
 
//很明显雷达应该安装在海岸线上 
//而为了满足一个点被覆盖那在区间[x - sqrt(d ^ 2 - y ^ 2), x + sqrt(d ^ 2 - y ^ 2)]之中必有一个雷达 
//现在就转换为一个区间覆盖问题:选尽量少的点使得每一个区间之内都有一个点 
//把这些区间按右端点排序,记录last为上次雷达安装的点,若一个区间的左端点>last,那这个区间就不能被之前的点覆盖
//更新last=该区间的右端点(贪心选择,右端点有几率覆盖更多的区间),ans++ 

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>

using namespace std;

int n;
double d;
double x[1010], y[1010];
double l[1010], r[1010];
int ra[1010], ans;
double last = -1000000000.0;

bool cmp(int a, int b) {
    return r[a] < r[b];
}

int main() {
    cin >> n >> d;
    for (int i = 1; i <= n; i++) {
        cin >> x[i] >> y[i];
        if (y[i] > d) {
            cout << -1;
            return 0;
        }
        l[i] = x[i] - sqrt(d * d - y[i] * y[i]);
        r[i] = x[i] + sqrt(d * d - y[i] * y[i]);
    }
    for (int i = 1; i <= n; i++) ra[i] = i;
    sort(ra + 1, ra + n + 1, cmp);
    for (int i = 1; i <= n; i++) {
        if (l[ra[i]] > last) {
            ans++;
            last = r[ra[i]];
        }
    }
    cout << ans;
    return 0;
}

 

落谷p1325雷达安装[计算几何]

原文:https://www.cnblogs.com/zcr-blog/p/11930442.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!