1 Востаннє редагувалося Q-bart (12.12.2014 17:03:10)

Тема: Задача

Доброго вечора!
Є така задачка

Прихований текст

Одного разу Сеньйор розповів Дракону, що минулого вечора він K
разів бачив над лісом дим. Як ви знаєте, диму без вогню не буває.
Дракон пригадав, що вчора він гуляв лісом та час від часу заради
розваги дмухав вогнем, як це інколи роблять всі поважні дракони.
Всього Дракон дмухав вогнем у N точках. Сеньйору раптом стало
цікаво – наскільки далеко він може побачити драконів дим?
Нехай відстань, на яку видно дим - R. Тоді кожного разу, коли
Дракон дмухає вогнем, дим можуть побачити лише ті, хто знаходиться
на відстані не більшій ніж R від дракона.
Знаючи координати хатинки Сеньйора, а також усіх місць, де
дмухав вогнем Дракон, скажіть, яка найменша можлива відстань R,
при якій Сеньйор міг бачити дим хоча б K разів.

Як думав розв'язувати я.. знайти всі відстані від точок, де був дим до будиночка..
Тоді нам треба знайти найменше R, якщо сеньйор бачив дим К разів: тобто якщо розташувати всі довжини в порядку зростання, то нам треба К-ну довжину...

program breathe;

var
  x1, y1, c: real;
  n, k, i, j: integer;
  x, y, a: array [1..100] of real;

begin
  readln(x1, y1);
  readln(n, k);
  for i := 1 to n do 
  begin
    readln(x[i], y[i]);
    a[i] := sqrt((sqr(x1 - x[i])) + (sqr(y1 - y[i])));
  end;
  
  for i := 1 to n - 1 do
    for j := 1 to n - j do
      if a[i] > a[i + 1] then begin
        c := a[i + 1];
        a[i + 1] := a[i];
        a[i] := c;
      end;
  writeln(a[k]);
end.

Але воно по тесту неправильно працює...

2

Re: Задача

Основна формула
http://uk.wikipedia.org/wiki/Віддаль_між_двома_точками

Мій розв'язок
#include <iostream>
#include <vector>    
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    int f, s;
    int n, k;    

    cin >> f >> s;
    cin >> n >> k;

    vector<double> x(n);
    vector<double> y(n);
    vector<double> dis(n);

    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    for (int i = 0; i < n; ++i)
        dis[i] = sqrt(((x[i] - f)*(x[i] - f)) + ((y[i] - s)*(y[i] - s)));

    for (int i = 0; i < n; ++i)
        sort(dis.begin(), dis.end());

    double max_dis = dis[0];

    for (int i = 1; i < k; ++i)
        max_dis = max(max_dis, dis[i]);
    
    cout << fixed << setprecision(8) << max_dis << endl;

    return 0;
}

3 Востаннє редагувалося Q-bart (12.12.2014 17:34:32)

Re: Задача

Joker написав:

Основна формула
http://uk.wikipedia.org/wiki/Віддаль_між_двома_точками

Мій розв'язок
#include <iostream>
#include <vector>    
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;

int main()
{
    int f, s;
    int n, k;    

    cin >> f >> s;
    cin >> n >> k;

    vector<double> x(n);
    vector<double> y(n);
    vector<double> dis(n);

    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];

    for (int i = 0; i < n; ++i)
        dis[i] = sqrt(((x[i] - f)*(x[i] - f)) + ((y[i] - s)*(y[i] - s)));

    for (int i = 0; i < n; ++i)
        sort(dis.begin(), dis.end());

    double max_dis = dis[0];

    for (int i = 1; i < k; ++i)
        max_dis = max(max_dis, dis[i]);
    
    cout << fixed << setprecision(8) << max_dis << endl;

    return 0;
}

Формула є, все рахує, проблема в чомусь дальше..
Дякую за розв'язок, але я не розумію на C++...

4

Re: Задача

Можливо проблема у тому, що потрібно вивести 7 чи 8 знаків після коми?

5

Re: Задача

Ні, я поки що пробую не на тестері, лише за прикладами вводу, виводу..

6

Re: Задача

код. Додав коментарі
#include <iostream>
#include <vector>    
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;
 
int main()
{
    int f, s;
    int n, k;    
 
// Вводимо дані
    cin >> f >> s;
    cin >> n >> k;
 
// Масиви
    vector<double> x(n);
    vector<double> y(n);
    vector<double> dis(n);
 
// Заповнення масивів
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
 // Рахую всі відстані
    for (int i = 0; i < n; ++i)
        dis[i] = sqrt(((x[i] - f)*(x[i] - f)) + ((y[i] - s)*(y[i] - s)));
 // Сортую всі відстані
    for (int i = 0; i < n; ++i)
        sort(dis.begin(), dis.end());
 
    double max_dis = dis[0];
 // Шукаю максимальну відстань
    for (int i = 1; i < k; ++i)
        max_dis = max(max_dis, dis[i]);
    
// Вивід 8 знаків після коми
    cout << fixed << setprecision(8) << max_dis << endl;
 
    return 0;
}
Подякували: Q-bart1

7 Востаннє редагувалося koala (12.12.2014 18:59:37)

Re: Задача

Q-bart написав:
    for j := 1 to n - j do

Оригінально...
Сортування уважно прогляньте - там якась єресь завелася.

Подякували: Q-bart1

8

Re: Задача

Joker написав:
код. Додав коментарі
#include <iostream>
#include <vector>    
#include <iomanip>
#include <algorithm>
#include <math.h>
using namespace std;
 
int main()
{
    int f, s;
    int n, k;    
 
// Вводимо дані
    cin >> f >> s;
    cin >> n >> k;
 
// Масиви
    vector<double> x(n);
    vector<double> y(n);
    vector<double> dis(n);
 
// Заповнення масивів
    for (int i = 0; i < n; ++i)
        cin >> x[i] >> y[i];
 // Рахую всі відстані
    for (int i = 0; i < n; ++i)
        dis[i] = sqrt(((x[i] - f)*(x[i] - f)) + ((y[i] - s)*(y[i] - s)));
 // Сортую всі відстані
    for (int i = 0; i < n; ++i)
        sort(dis.begin(), dis.end());
 
    double max_dis = dis[0];
 // Шукаю максимальну відстань
    for (int i = 1; i < k; ++i)
        max_dis = max(max_dis, dis[i]);
    
// Вивід 8 знаків після коми
    cout << fixed << setprecision(8) << max_dis << endl;
 
    return 0;
}

Дякую, в мене алгоритм збігається, помилка десь в написанні..

9

Re: Задача

koala написав:
Q-bart написав:
    for j := 1 to n - j do

Оригінально...
Сортування уважно прогляньте - там якась єресь завелася.

Дуже  дякую, точно допустився помилки...
Але переглядав цей кусок, не один раз - нічого не бачив.. Як навчитися бачити такі дрібнички???

10

Re: Задача

Запустіть програму крок за кроком і перевіряйте чи вона все правильно робить.

p.s. у VS це клавіша F10

11

Re: Задача

Joker написав:

Запустіть програму крок за кроком і перевіряйте чи вона все правильно робить.

p.s. у VS це клавіша F10

Порада Koalи допомогла..