雷达安装 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 称为 Ox 轴上到点 (x,y) 的距离等于 d 的两个点，因此我们有一个正方形三角形 (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);

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

雷达安装 UVA

Radar Installation UVA

c++

algorithm

greedy