比赛 贪心题目练习 评测结果 AAAAAAAAAA
题目名称 监控安装 最终得分 100
用户昵称 Cogito 运行时间 0.036 s
代码语言 C++ 内存使用 3.38 MiB
提交时间 2025-03-22 10:08:39
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;

struct Node {
    double bi, en;
};
int n, r, res = 1;
Node a[1005];

bool cmp (Node a, Node b) {
    return a.en < b.en;
}

int main () {
    freopen("monitor.in","r", stdin);
    freopen("monitor.out","w",stdout);
    cin >> n >> r;
    int r1 = r * r;
    int x, y;
    for (int i = 1; i <= n; i++) {
        cin >> x >> y;
        if (y > r) {
            cout << -1; 
            return 0;
        }
        double m = sqrt(r1 - y * y); a[i].bi = x - m; a[i].en = x + m;
    } 
    sort(a+1, a+1+n, cmp);
    
    double leida = a[1].en;
    for (int i = 2; i <= n; i++) {
        if (leida < a[i].bi) res++, leida = a[i].en;
    }
    cout << res << endl;
	return 0;
}