Радарная установка 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);
Это для расчета дальности, которую мы можем поставить радаром, который может покрыть остров 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) первого острова, который может помочь покрыть максимальное количество островов справа от этого острова, и продолжить этот процесс со следующим открытым островом до конца.
Другие решения