#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <iomanip>
using namespace std;
void Dijkstra_vu(vector<vector<pair<float, int>>> graph, int v_start, int u_end);
// Ввод графа из файла.
void test(string filename)
{
ifstream fin(filename);
vector<vector<pair<float, int>>> graph;
int N = 0; // Количество аэропортов.
float D = 0.0f; // Максимальное расстояние без посадки.
int A = 0; // Где я есть.
int B = 0; // Куда мне надо.
fin >> N;
fin >> D;
fin >> A;
fin >> B;
graph.resize(N);
int grad1 = 0, grad2 = 0;
float rad = 3.1415927f / 180.0f;
vector<pair<float, float>> coordinates;
for (int i = 0; i < N; i++)
{
fin >> grad1; fin >> grad2;
coordinates.push_back({ grad1 * rad, grad2 * rad });
}
for (int i = 0; i < N; i++)
{
for (int j = i + 1; j < N; j++)
{
// Расстояние между i и j портами.
float dbtw = 2.0f * asin(sqrt(pow((sin((coordinates[i].first - coordinates[j].first) / 2.0f)), 2) + cos(coordinates[i].first) * cos(coordinates[j].first) * pow((sin((coordinates[i].second - coordinates[j].second) / 2.0f)), 2)));
if (dbtw <= D || dbtw < 1e-7f)
{
graph[i].push_back({ dbtw, j });
graph[j].push_back({ dbtw, i });
}
}
}
Dijkstra_vu(graph, A - 1, B - 1);
}
// Поиск кратчайшего пути между двумя вершинами.
void Dijkstra_vu(vector<vector<pair<float, int>>> graph, int A, int B)
{
vector<float> d(graph.size(), FLT_MAX); // Кратчайшие расстояния до вершины.
priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> Q;
vector<bool> isUsed(graph.size(), false); // Множество вершин, для которых вычислены кратчайшие пути из начальной.
d[A] = 0.0f;
Q.push({ 0.0f, A }); // { Расстояние, Номер_вершины }.
while (!Q.empty())
{
auto v_min = Q.top(); // Взята ближайшая вершина.
Q.pop();
int v = v_min.second; // Номер вершины v.
if (isUsed[v])
continue;
isUsed[v] = true;
// Для каждой вершины u, смежной с v:
for (pair<float, int> e : graph[v])
{
int u = e.second; // Номер вершины u.
float len_vu = e.first; // Вес ребра со смежной.
// Добавление в очередь вершины u, смежной с v.
if (d[u] > d[v] + len_vu)
{
d[u] = d[v] + len_vu;
Q.push({ len_vu, u });
}
}
if (isUsed[B])
{
cout << fixed;
cout.precision(3);
cout << d[B] << endl;
break;
}
}
if (!isUsed[B])
cout << -1 << endl;
}
void main()
{
vector<string> in
{
"input01.txt",
"input02.txt",
"input03.txt",
"input04.txt",
"input05.txt",
"input06.txt",
"input07.txt",
"input08.txt",
"input09.txt",
"input10.txt",
"input11.txt",
"input12.txt",
"input13.txt",
"input14.txt",
"input15.txt",
"input16.txt",
"input17.txt",
"input18.txt",
"input19.txt",
"input20.txt",
"input21.txt",
"input22.txt",
"input23.txt",
"input24.txt",
"input25.txt",
"input26.txt",
"input27.txt",
"input28.txt",
"input29.txt",
"input30.txt",
"input31.txt",
"input32.txt",
};
vector<string> out
{
"output01.txt", // 1.571
"output02.txt", // -1
"output03.txt", // 3.142
"output04.txt", // 0.000
"output05.txt", // -1
"output06.txt", // 0.017
"output07.txt", // 0.000
"output08.txt", // -1
"output09.txt", // -1
"output10.txt", // -1
"output11.txt", // 0.868
"output12.txt", // 2.653
"output13.txt", // -1
"output14.txt", // -1
"output15.txt", // -1
"output16.txt", // 3.011
"output17.txt", // -1
"output18.txt", // -1
"output19.txt", // -1
"output20.txt", // 1.957
"output21.txt", // -1
"output22.txt", // -1
"output23.txt", // 2.484
"output24.txt", // 1.346
"output25.txt", // -1
"output26.txt", // 2.915
"output27.txt", // 0.933
"output28.txt", // 2.739
"output29.txt", // -1
"output30.txt", // 2.435
"output31.txt", // 1.668
"output32.txt", // 0.833
};
for (auto &obj : in)
test(obj);
int y;
}