【codeforces】Radar Installation

电玩女神 2022-09-24 04:23 106阅读 0赞

![这里写图片描述][20160723200118449]  
![这里写图片描述][20160723200126480]  
别说话，看注释。

#include<stdio.h>//此题犯了一个超级二，又很可能被忽略而出现的问题
                     //输出-1的时候我竟然忘了Cace %d:格式了 / 大哭/哇/ 
    #include<math.h>
    #include<algorithm>
    using namespace std;
    struct note {
        double front;
        double back;
    } s[1010];
    bool judge(note a,note b) {
        if(a.front==b.front)//因为后面的圆包含在内的话前面的圆一定在内，
    //而后面圆不在内的话正好加一（这俩一定用一个雷达的，主要是和前面一个圆比较）
            return a.back>b.back;
        return a.front<b.front;
    }
    int main() {
        double d;
        int p=0,n;
        while(scanf("%d %lf",&n,&d),n||d) {
            double x,y,mark=1;
            double temp;
            for(int l=1; l<=n; l++) {
                scanf("%lf %lf",&x,&y);
                temp=d*d-y*y;
                if(temp<0||d<0)//
                    mark=0;
                else if(mark) {
                    s[l].front=x+sqrt((double)d*d-(double)y*y);
                    s[l].back=x-sqrt((double)d*d-(double)y*y);
                }
            }
            if(!mark) {
                printf("Case %d: -1\n",++p);
                continue;
            }
            int sum=1;
            sort(s+1,s+n+1,judge);
            temp=s[1].front;
            for(int l=2; l<=n; l++) {
                if(temp<s[l].back) {
                    sum++;
                    temp=s[l].front;
                }
            }
            printf("Case %d: %d\n",++p,sum);
        }
        return 0;
    }

[http://acm.hust.edu.cn/vjudge/contest/123357\#problem/G][http_acm.hust.edu.cn_vjudge_contest_123357_problem_G]

[20160723200118449]: /images/20220720/196785dcb8cc462ca986980ca7a4c7e4.png
[20160723200126480]: /images/20220720/9d66faca99294e258762fc0c8d06a7c2.png
[http_acm.hust.edu.cn_vjudge_contest_123357_problem_G]: http://acm.hust.edu.cn/vjudge/contest/123357#problem/G