雷达装置UVA

Question

我试图理解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);

谁能指点我一下吗？谢谢。

Answer 1

关于你的第一个问题：

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

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

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

所以，看上面的图像，要在(x，y)位置覆盖一个岛屿，我们可以把雷达放在从x - (d^2 - y^2)到x + (d^2 - y^2)的范围内。

一些解释：

调用点A和B在与点(x，y)相距等于d的Ox轴上的两点，所以我们有一个正方形三角形(A，(x，y)，(x,0))，利用Pythagoras定理，我们可以很容易地计算出A和B的位置。

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

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

关于你的第二个问题：

Also, why is sorting being used?

sort(inter, inter + n);

为了覆盖所有岛屿，我们需要把雷达从最左边的岛屿开始，然后继续到第二个最远的岛屿.直到我们覆盖所有岛屿。因此，我们可以贪婪地完成这一过程，将雷达放在第一个岛屿的右侧x + (d^2 - y^2)上，这可以帮助覆盖这个岛右侧的最大数量的岛屿，并在下一个未发现的岛屿上继续这一过程，直到最后。