Дано: два отрезка на плоскости, найти кратчайшее расстояние между ними. Можно как то обойтись без математики, ну то есть это просто решается, но мне интересно решение с помощью бинарного поиска. Моя идея: перебрать точки на первом отрезке и на втором, и вычислять кратчайшее расстояние. У меня есть реализация, наименьшего расстояния между точкой и отрезком, с помощью бинарного поиска, но как это реализовать для двух отрезков?
#include <iostream>
#include <cmath>
#include <algorithm>
#define ld long double
using namespace std;
ld mindiff;
ld distance(ld xa, ld ya, ld xb, ld yb) {
return sqrt((xb - xa)*(xb - xa) + (yb - ya)*(yb - ya));
}
ld mindifference(ld x1, ld y1, ld x2, ld y2, ld x3, ld y3) {
ld l = distance(x1, y1, x3, y3);
ld r = distance(x2, y2, x3, y3);
for (int i = 0; i <= 100; i++) {
if (l <= r) {
r = distance((x1 + x2) / 2, (y1 + y2) / 2, x3, y3);
x2 = (x1 + x2) / 2;
y2 = (y1 + y2) / 2;
}
else {
l = distance((x1 + x2) / 2, (y1 + y2) / 2, x3, y3);
x1 = (x1 + x2) / 2;
y1 = (y1 + y2) / 2;
}
}
return l;
}
int main() {
ld x1, y1, x2, y2, xa, ya;
cin >> x1 >> y1 >> x2 >> y2;
cin >> xa >> ya;
cout << fixed;
cout.precision(6);
cout << mindifference(x1, y1, x2, y2, xa, ya) << endl;
return 0;
}