c++ - 雷达安装UVA

我正在尝试了解UVA问题1193的示例解决方案：
问题陈述：
解决方案：

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

using namespace std;

#define Max 10000
const double eps = 1e-10;

struct Interval {
    double st, en;
    Interval() {}
    Interval(double s, double e) {
        st = s, en = e;
    }
    bool operator < (const Interval &i) const {
        return (i.en == en) ? (st < i.st) : (en < i.en);
    }
};
long double x[Max], y[Max];
Interval inter[Max];

//bujhlam na baal
int main(void) {
    int n, d, testcase = 0;
    while(scanf("%d %d", &n, &d) == 2 && !(n == 0 && d == 0)) {
        for(int i = 0; i < n; i++)
            scanf("%Lf %Lf", &x[i], &y[i]);
        int count = 0, ok = true;
        for(int i = 0; i < n; i++) {
            if(d < y[i]) { // if island is out of radar radious
                ok = false; // that means at least one of the islands is not reachable results in -1
                break;
            } else {
                long double sqrtd = sqrt( d * d - y[i] * y[i] );
                inter[i] = Interval(x[i] - sqrtd, x[i] + sqrtd);
            }
        }
        if(!ok) {
            printf("Case %d: %d\n", ++testcase, -1);
            continue;
        }
        sort(inter, inter + n);

        for(int i = 0; i < n;) {
            int j;
            for(j = 0; j < n; j++) {
                if(inter[j].st > inter[i].en)
                    break;
            }
            i = j;
            count++;
        }
        printf("Case %d: %d\n", ++testcase, count);
    }
    return 0;
}

我似乎不能按照作者的方法来解决这个问题。让我卡住的部分如下所示：

long double sqrtd = sqrt( d * d - y[i] * y[i] );
inter[i] = Interval(x[i] - sqrtd, x[i] + sqrtd);

好像作者在用毕达哥拉斯定理？我看不出这有什么用。
另外，为什么要使用排序？

sort(inter, inter + n);

有人能开导我吗谢谢。

最佳答案

对于你的第一个问题：

long double sqrtd = sqrt( d * d - y[i] * y[i] );
inter[i] = Interval(x[i] - sqrtd, x[i] + sqrtd);

这是为了计算我们可以放置一个可以覆盖岛屿的雷达的距离。

            . (x,y)
           /|\
          / | \ d
 0 ______/__|__\________
        A   x   B

所以，看上面的图片，为了在（x，y）位置覆盖一个岛，我们可以在i到x - (d^2 - y^2)的范围内放置一个雷达
一些解释：
调用点A和B的牛心轴上的两点距离（x，y）等于x + (d^2 - y^2)，因此我们有一个正方形三角形（a，（x，y），（x，0）），使用毕达哥拉斯定理，我们可以很容易地计算A和B的位置。

A = x - (d^2 - y^2)

B = x + (d^2 + y^2)

关于你的第二个问题：

Also, why is sorting being used?

sort(inter, inter + n);

为了覆盖所有的岛屿，我们需要从最左边的岛屿开始放置雷达，并继续到第二个最左边的岛屿直到我们覆盖所有岛屿。因此，我们可以贪婪地进行这个过程，通过将雷达放在第一岛的右端d，这可以帮助覆盖这个岛右边的最大岛屿数，并继续下一个未被覆盖的岛屿直到结束。