e-olymp 396. Дождь

24/11/2021 by Александр Мармалюк

Условие

Капля дождя падает вертикально вниз с большой высоты на землю. На пути у капли могут встретиться препятствия, которые изменяют ее путь к земле.

Напишите программу, которая по координате $\ x_0\ $ точки появления капли над землей вычисляет координату $x$ точки соприкосновения капли с землей $\ \left(y = 0\right).\ $ Будем рассматривать двумерный вариант (на плоскости) этой задачи. Пусть препятствия – это наклонные непересекающиеся отрезки, а капля имеет точечные размеры. Капля падает вертикально вниз из точки, расположенной выше любого из препятствий. Если капля при падении соприкасается с отрезком-препятствием, то она стекает по отрезку вниз, пока не упадет вертикально вниз с меньшего по высоте конца отрезка.

Входные данные

Во входном файле в первой строке содержатся два целых числа через пробел – координата $\ x_0\ $ точки появления капли $\ \left( 0 \lt x_0 \lt 10000\right)\ $ и количество отрезков-препятствий $\ N\ (0 \leqslant N \leqslant 100).\ $ Далее следует $\ N\ $ строк, каждая из которых содержит четыре разделенные пробелами числа $\ x_1,\ $ $\ y_1,\ $ $\ x_2,\ $ $\ y_2\ $ – координаты левого и правого концов отрезка-препятствия (все числа целые и находятся в диапазоне от $\ 0$\ до $\ 10000\ $, $\ x_1 \lt x_2,$ $y_1 \neq y_2.\ $ Отрезки не пересекаются и не соприкасаются.

Выходные данные

В выходной файл вывести одно целое число – координату $\ x\ $ точки соприкосновения капли с землей.

Тесты

Входные данные Выходные данные

30 4 25 35 40 30 1 32 20 30 33 22 50 29 18 10 33 19	18
7 5 1 6 10 8 5 3 8 2 6 10 11 9 9 10 14 12 6 6 12 7	8
4 4 1 1 3 3 2 3 0 6 7 3 5 2 6 5 9 6	4
8 3 8 6 2 4 7 4 9 3 6 1 10 2	2
2 3 5 9998 0 10000 7 9996 11 9994 4 9996 9 9993	9

Код программы

#include <iostream>
#include <cmath>
#include <vector>
#define MAX_Y 10000;
using namespace std;
struct slide {
    double x1;
    double y1;
    double x2;
    double y2;
};
//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]
double f (slide x, double x0) {
    double dx = x.x2 - x.x1;
    double dy = x.y2 - x.y1;
    return ((dy*(x0 - x.x1))/dx + x.y1);
}
vector <slide> roof; //вектор всех крыш
//считывание и заполнение данных
void read (int n) {
    while (n--) {
        double a, b, c, d;
        slide x;
        cin >> a >> b >> c >> d;
        if (a < c) {
            x.x1 = a;
            x.y1 = b;
            x.x2 = c;
            x.y2 = d;
        }
        else
        {
            x.x1 = c;
            x.y1 = d;
            x.x2 = a;
            x.y2 = b;
        }
        roof.push_back(x);
    }
}
int main() {
    int n, x, y = MAX_Y + 1;
    slide a;
    cin >> x >> n;
    if (n == 0) {
        cout << x;
        return 0;
    }
    read (n);
    while (roof.size()) {
        int index = -1;
        int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей
        bool no_projection = true;
        for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х
            if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?
                no_projection = false;
                if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?
                    value = f(roof[i], x);
                    index = i;
                }
            }
            if (min(roof[i].y1, roof[i].y2) > y) {  //крыша целиком осталась выше?
                roof.erase(roof.begin() + i);
                i--;
            }
        }
        if ((roof.size() == 0) or (no_projection)) {  //если удалили все крыши или свободно падает на землю
            cout << x;
            return 0;
        }
        if (roof[index].y1 < roof[index].y2)  //какой конец крыши ниже?
            x = roof[index].x1;
        else
            x = roof[index].x2;
        y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату
        roof.erase(roof.begin() + index);
    }
    cout << x;
    return 0;
}

#include <iostream>

#include <cmath>

#include <vector>

#define MAX_Y 10000;

using namespace std;

struct slide {

double x1;

double y1;

double x2;

double y2;

};

//высота соприкосновения капли с крышей [ур-ние прямой по 2-м точкам]

double f (slide x, double x0) {

double dx = x.x2 - x.x1;

double dy = x.y2 - x.y1;

return ((dy*(x0 - x.x1))/dx + x.y1);

}

vector <slide> roof; //вектор всех крыш

//считывание и заполнение данных

void read (int n) {

while (n--) {

double a, b, c, d;

slide x;

cin >> a >> b >> c >> d;

if (a < c) {

x.x1 = a;

x.y1 = b;

x.x2 = c;

x.y2 = d;

}

else

{

x.x1 = c;

x.y1 = d;

x.x2 = a;

x.y2 = b;

}

roof.push_back(x);

}

int main() {

int n, x, y = MAX_Y + 1;

slide a;

cin >> x >> n;

if (n == 0) {

cout << x;

return 0;

}

read (n);

while (roof.size()) {

int index = -1;

int value = -1; //предполагаемая высока соприкосновения капли со следующей крышей

bool no_projection = true;

for (int i = 0; i < roof.size(); i++) { //поиск самой высокой крыши в точке х

if ((x <= roof[i].x2) and (x >= roof[i].x1)) { //капля проектируется на и-тую крышу?

no_projection = false;

if ((f(roof[i], x) > value) and (f(roof[i], x) < y)) { //и-тая крыша выше ранее найденной?

value = f(roof[i], x);

index = i;

}

if (min(roof[i].y1, roof[i].y2) > y) { //крыша целиком осталась выше?

roof.erase(roof.begin() + i);

i--;

}

if ((roof.size() == 0) or (no_projection)) { //если удалили все крыши или свободно падает на землю

cout << x;

return 0;

}

if (roof[index].y1 < roof[index].y2) //какой конец крыши ниже?

x = roof[index].x1;

else

x = roof[index].x2;

y = min(roof[index].y1, roof[index].y2); //сохранили новую ординату

roof.erase(roof.begin() + index);

}

cout << x;

return 0;

}

Решение

Для удобства создадим структуру slide, которая будет описывать координаты концов отрезка-крыши. Также будем считать, что первый конец отрезка находится левее (для этого будем менять местами точки в случае необходимости).
Будем представлять каждую крышу как отрезок прямой на плоскости. Для этого применим уравнение прямой по двум точкам, принадлежащим этой прямой:
$$\frac{x — x_1}{x_2 — x1}=\frac{y — y_1}{y_2 — y_1}$$
Чтобы проверить, может ли капля в текущий момент проектироваться на некоторую крышу, надо проверить, находится ли абсцисса капли между абсциссами концов отрезка-крыши, а также найти ту крышу, которая в абсциссе капли «выше всех» (другими словами, у какой из прямых, которым принадлежат те отрезки, на которые проектируется капля, наибольшее значение ординаты в абсциссе капли). Для этого создадим функцию, которая и будет возвращать искомое значение ординаты. Также важно убедиться в том, что эта крыша находится ниже текущего положения капли. Заметим, что если некоторая крыша целиком находится выше капли, то мы на неё уже никогда не попадем, поэтому её нужно удалить из вектора. Найдя нужную крышу, определим новые координаты капли после того, как она скатится по этой крыше. Если капля в свободном падении и на её пути больше нет препятствий (крыш не осталось или нет такой, на которую проектируется капля), то текущая абсцисса капли и будет ответом на задачу.

Ссылки

Условие задачи на eolymp.com
Решение задачи на ideone.com

Related Images:

e-olymp 497. Лентяй

21/05/2019 by Андрей Зиновьев

Задача

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные	Вывод программы
2 1 1 2 2 1 2 3 4	YES NO
1 1 5 6	YES
2 2 1 4 7 9 3 1 30 2 5 5 10	NO YES

Continue reading →

Related Images:

e-olymp 8357. Точка в многоугольнике

08/12/2018 by Руслан Масальский

Задача взята с сайта e-olymp

Условие

Как известно, простой многоугольник — это фигура, состоящая из непересекающихся отрезков («сторон»), соединённых попарно с образованием замкнутого пути. По заданному простому многоугольнику и точке требуется определить, лежит ли эта точка внутри или на границе этого многоугольника или вне его.

Входные данные

В первой строке заданы три числа: [latex]n (3 \leq n \leq 10^5)[/latex] и координаты точки. Далее в [latex]n[/latex] строках заданы по паре чисел — координаты очередной вершины простого многоугольника в порядке обхода по или против часовой стрелки.

Выходные данные

Вывести строку «YES«, если заданная точка содержится в приведённом многоугольнике или на его границе, и «NO» в противном случае.

Тесты

№	Inputs	Outputs
1	3 0 0 1 0 0 1 1 1	NO
2	4 3 2 0 0 1 5 5 5 6 0	YES
3	8 2 1 0 0 0 4 4 4 4 0 3 0 3 2 1 2 1 0	NO
4	8 4 3 0 0 0 4 4 4 4 0 3 0 3 2 1 2 1 0	YES
5	6 1 1 0 0 0 2 1 4 2 2 2 0 1 3	NO

Код

#include <iostream> 
#include <cmath>
typedef double long dl;
using namespace std;
const double E = 1e-6;
bool on_edge(dl x, dl y, dl x1, dl y1, dl x2, dl y2) {
    bool res = false;
    if (fabs(x2 - x1) < E) {
        if (fabs(x - x1) < E && y > min(y1, y2) - E && y - E < max(y1, y2)) res = true;
    } else {
        x -= x1;
        y -= y1;
        x2 -= x1;
        y2 -= y1;
        if (x - E < max(x1, x2) && x > min(x1, x2) - E && fabs(x2 * y - y2 * x) < E) {
            res = true;
        }
    }
    return res;
}
bool cross(dl x0, dl y0, dl x1, dl y1, dl x2, dl y2){
    return (y1 < y0 && y2 > y0 - E || y2 < y0 && y1 > y0 - E) && (y0 * (x1 - x2) + y1 * x2 - x1 * y2) / (y1 - y2) < x0;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    dl x0, y0, xs, ys, xt, yt, xi, yi;
    int n;
    cin >> n >> x0 >> y0;
    cin >> xs >> ys;
    xt = xs;
    yt = ys;
    bool par_am = false;
    bool on_side = false;
    n--;
    while (n-- && !on_side) {
        cin >> xi >> yi;
        if (on_edge(x0, y0, xt, yt, xi, yi)) {
            on_side = true;
        }
        if (cross(x0, y0, xt, yt, xi, yi)) {
            par_am = !par_am;
        }
        xt = xi;
        yt = yi;
    }
    if (on_edge(x0, y0, xt, yt, xs, ys)) {
        on_side = true;
    }
    if (cross(x0, y0, xt, yt, xs, ys)) {
        par_am = !par_am;
    }
    cout << (par_am || on_side ? "YES" : "NO");
    return 0;
}

#include <iostream>

#include <cmath>

typedef double long dl;

using namespace std;

const double E = 1e-6;

bool on_edge(dl x, dl y, dl x1, dl y1, dl x2, dl y2) {

bool res = false;

if (fabs(x2 - x1) < E) {

if (fabs(x - x1) < E && y > min(y1, y2) - E && y - E < max(y1, y2)) res = true;

} else {

x -= x1;

y -= y1;

x2 -= x1;

y2 -= y1;

if (x - E < max(x1, x2) && x > min(x1, x2) - E && fabs(x2 * y - y2 * x) < E) {

res = true;

}

return res;

}

bool cross(dl x0, dl y0, dl x1, dl y1, dl x2, dl y2){

return (y1 < y0 && y2 > y0 - E || y2 < y0 && y1 > y0 - E) && (y0 * (x1 - x2) + y1 * x2 - x1 * y2) / (y1 - y2) < x0;

}

int main() {

ios::sync_with_stdio(0);

cin.tie(0);

cout.tie(0);

dl x0, y0, xs, ys, xt, yt, xi, yi;

int n;

cin >> n >> x0 >> y0;

cin >> xs >> ys;

xt = xs;

yt = ys;

bool par_am = false;

bool on_side = false;

n--;

while (n-- && !on_side) {

cin >> xi >> yi;

if (on_edge(x0, y0, xt, yt, xi, yi)) {

on_side = true;

}

if (cross(x0, y0, xt, yt, xi, yi)) {

par_am = !par_am;

}

xt = xi;

yt = yi;

}

if (on_edge(x0, y0, xt, yt, xs, ys)) {

on_side = true;

}

if (cross(x0, y0, xt, yt, xs, ys)) {

par_am = !par_am;

}

cout << (par_am || on_side ? "YES" : "NO");

return 0;

}

Решение

Проверять на то, находится ли точка внутри многоугольника, будем так. Берём нашу точку и от нее проводим луч влево параллельно оси абсцисс.
Считаем количество пересечений луча со сторонами многоугольника.
Если количество пересечений чётно, то точка лежит вне многоугольника, а если количество пересечений нечётно, то точка лежит внутри многоугольника.
Нужно еще учесть момент, когда точка лежит на одной из сторон.

x0, y0 — координаты нашей точки.
xs, ys — координаты самой первой точки, они нам нужны чтобы проверить пересечение луча со стороной, образованной первой и последней точками.
xi, yi — координаты точки которую вводим.
xt, yt — координаты предыдущей точки, нужны для того, чтобы образовать сторону.
par_am — (parity of amount) хранит четность количества пересечений луча со сторонами. Если чётное количество пересечений, то par_am = false, если нечётное, то par_am = true.
on_side — если мы узнали, что точка лежит на одной из сторон, то дальше ничего искать не нужно.

Функция on_edge() рассматривает два случая:

Если сторона параллельна оси [latex]Oy[/latex], посчитаем условие нахождения между минимальной и максимальной [latex]y[/latex]-координатами. Если оно справедливо, проверяем на равенство [latex]x[/latex]-координат.
Для удобства мы подвинет отрезок и точку так чтоб начало отрезка лежало в точке [latex](0,0)[/latex]. После это проверяем находится ли точка по координате [latex]x[/latex] между концов (включительно) отрезка. Остается сравнить тангенс угла между осью [latex]Ox[/latex] и вектором [latex]x_2[/latex] [latex]y_2[/latex]с тангенсом угла между осью [latex]Ox[/latex] и вектором [latex]x[/latex] [latex]y[/latex] и если они равны, то точка [latex]x[/latex] [latex]y[/latex] лежит на отрезке (стороне) [latex]x_1, y_1, x_2, y_2 [/latex].

Считываем и запоминаем первую точку. Дальше считываем по точке, которая вместе с предыдущей образует сторону. Делаем проверку:

Лежит ли точка [latex]x_0[/latex] [latex]y_0[/latex] на этой стороне.
Пересекает ли луч сторону.

Чтобы проверить пересекает ли луч сторону делаем:

Проверяем лежат ли две точки по разные стороны луча
Строим уравнение прямой вида [latex]y = kx +b[/latex], проходящее через две точки [latex]x_i, y_i, x_t, y_t [/latex]выглядит оно так:
[latex]y = \frac{y_i-y_t}{x_i-x_t} \cdot x+(y_i-\frac{y_i-y_t}{x_i-x_t} \cdot x_i )[/latex]
Подставив вместо [latex]y[/latex] [latex]y_0[/latex], получаем что [latex]x[/latex] равен
[latex]\frac{y_0 \cdot x_i-y_0 \cdot x_t+y_i \cdot x_t-x_i \cdot y_t} {y_i-y_t}[/latex] И он должен быть меньше [latex]x_0[/latex], так как луч направлен влево.

Сложность [latex]O(n)[/latex], где [latex]n[/latex] — количество точек в многоугольнике.

Ссылки

ideone
e-olymp

Related Images:

e-olimp 197. Отрезок и окружности

17/02/2018 by Антон Джашимов

Задача

На плоскости задана система концентрических окружностей, центры которых находятся в начале координат, а радиусы равны $1, 2, 3, \ldots$ Также на плоскости задан отрезок, концы которого находятся в точках [latex] (x_{1};y_{1}) [/latex], [latex] (x_{2};y_{2}) [/latex].
Необходимо найти число общих точек этого отрезка и указанной системы окружностей.

Входные данные

Первая строка входного файла содержит 4 целых числа [latex]x_{1}[/latex], [latex]y_{1}[/latex], [latex]x_{2}[/latex], [latex]y_{2}[/latex]. Эти числа не превосходят $10^3$ по абсолютной величине. Заданный отрезок имеет ненулевую длину.

Выходные данные

В выходной файл выведите ответ на задачу.

Тесты

Входные данные	Выходные данные
-1 -1 1 1	2
-1 1 1 1	1
1 1 2 1	1
-5 -5 5 -5	5
-10 10 -10 10	28

Код программы

#include <iostream>
#include <cmath>
using namespace std;
int main()
{
    const float e = 10e-8;
    double x1, y1, x2, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    double d, a, b;
    d = abs((y2 * x1 - x2 * y1) / sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
    //Растояние до точки на отрезке, ближайщей к началу координат
    a = sqrt(x1 * x1 + y1 * y1);
    //Растояние от начала координат до первой точки
    b = sqrt(x2 * x2 + y2 * y2);
    //Растояние от начала координат до второй точки
    int count = 0;
    if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) or (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))
        //проверка первого условия
        count = (int)(max(a, b) + e) - (int)(min(a, b) - e);
    else {
        //второе условие
        count = (int)(a + e) - (int)(d - e);
        count = count + (int)(b + e) - (int)(d - e);
        if ((abs(round(d) - d) < e) and (abs(d) > e)) {
            //проверка крайнего случая
            count--;
        }
    }
    cout << count;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

const float e = 10e-8;

double x1, y1, x2, y2;

cin >> x1 >> y1 >> x2 >> y2;

double d, a, b;

d = abs((y2 * x1 - x2 * y1) / sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));

//Растояние до точки на отрезке, ближайщей к началу координат

a = sqrt(x1 * x1 + y1 * y1);

//Растояние от начала координат до первой точки

b = sqrt(x2 * x2 + y2 * y2);

//Растояние от начала координат до второй точки

int count = 0;

if ((2 * x1 * x1 - 2 * x1 * x2 + 2 * y1 * y1 - 2 * y1 * y2 < 0) or (2 * x2 * x2 - 2 * x1 * x2 + 2 * y2 * y2 - 2 * y1 * y2 < 0))

//проверка первого условия

count = (int)(max(a, b) + e) - (int)(min(a, b) - e);

else {

//второе условие

count = (int)(a + e) - (int)(d - e);

count = count + (int)(b + e) - (int)(d - e);

if ((abs(round(d) - d) < e) and (abs(d) > e)) {

//проверка крайнего случая

count--;

}

cout << count;

return 0;

}

Решение задачи

Для начала рассмотрим первое условие. Пусть наш отрезок таков, что при движении от одного края к другому, расстояние до начала координат возрастает. Для такого отрезка ответ очевиден — это количество целых чисел между расстояниями от начала координат до обоих концов отрезка. Условие из шестнадцатой строчки кода получилось путем приведения подобных и раскрытия скобок следующих неравенств:
[latex]x_{1}^{2}+y_{1}^{2}-x_{2}^{2}-y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0[/latex] и [latex]-x_{1}^{2}-y_{1}^{2}+x_{2}^{2}+y_{2}^{2}+(x_{1}-x_{2})^{2}+(y_{1}-y_{2})^{2}<0[/latex]

Иначе сведем данную задачу к рассмотренной выше. Для этого необходимо найти на отрезке точку, ближайшую к началу координат. Таким образом исходный отрезок разбивается на два новых, для которых выполнено условие из простой задачи. Также следует рассмотреть крайний случай, а именно, если ближайшая к [latex] (0;0) [/latex] точка находится на целом расстоянии от начала координат. В этом случае мы посчитаем это пересечение дважды, поэтому необходимо уменьшить ответ на единицу.

Стоит заметить, что находить саму ближайшую точку нет необходимости. Достаточно найти лишь расстояние до нее. Также мы добавляем маленькую константу [latex]\varepsilon=10^{-8}[/latex] к большему расстоянию до конца отрезка и отнимаем из меньшего, чтобы избежать случая нахождения какой-либо точки отрезка на окружности. В противном случае решение задачи будет работать не корректно.

Ссылки

Условие задачи на e-olymp

Код решения

Related Images:

Ю2.30. Расстояние между отрезками

12/10/2016 by Тимур Фирсов

Задача

Задача из сборника задач по программированию Юркина А.Г. 2002 г.
Найти расстояние между двумя между двумя произвольно заданными на плоскости отрезками [latex]AB[/latex] и [latex]CD[/latex].

Входные данные:

Координаты концов первого отрезка [latex]A[/latex] [latex](x_a, y_a)[/latex], [latex]B[/latex] [latex](x_b, y_b)[/latex].
Координаты концов второго отрезка [latex]C[/latex] [latex](x_c, y_c)[/latex], [latex]D[/latex] [latex](x_d, y_d)[/latex].

Выходные данные:

Расстояние между отрезками [latex]min[/latex].

Тесты

	Входные данные								Выходные данные
№	[latex]x_a[/latex]	[latex]y_a[/latex]	[latex]x_b[/latex]	[latex]y_b[/latex]	[latex]x_c[/latex]	[latex]y_c[/latex]	[latex]x_d[/latex]	[latex]y_d[/latex]	[latex]min[/latex]
1	1	1	2	1	3	1	4	1	1
2	0	0	5	5	1	1	2	2	0
3	0	1	3	3	5	3	6	4	2
4	0	0	7	0	0	8	5	3	3
5	5	5	10	10	5	9	6	12	2.8284
6	2	1	3	5	0	0	0	5	2
7	-3	0	3	0	0	-3	0	3	0

Код программы

#include <iostream>
#include <cmath>
using namespace std;

double ras(double x1, double y1, double x2, double y2, double x3, double y3){
    double k,d;
    if(x1==x2){ //Если отрезок вертикальный - меняем местами координаты каждой точки.
    swap(x1, y1);
    swap(x2, y2);
    swap(x3, y3);
    }
    k=(y1-y2)/(x1-x2);//Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок.
    d=y1-k*x1;
    double xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1);
    double dl=-1;
    if((xz<=x2&&xz>=x1)||(xz<=x1&&xz>=x2)) dl=sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d));//Проверим лежит ли основание высоты на отрезке.
    return dl;
}
int main() {
    double xa, xb, ya, yb, xc, xd, yc, yd, dl, dl1, dl2, dl3, dl4, min=-1,o,o1,o2,t=-2,s=-2;
    cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;
    o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc);
    o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa);
    o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya);
    if(o!=0){
        t=o1/o;
        s=o2/o;
    }
    if((t>=0&&s>=0)&&(t<=1&&s<=1))min=0;//Проверим пересекаются ли отрезки.
    else{ 
        //Найдём наименьшую высоту опущенную из конца одного отрезка на другой.
        dl1=ras(xa,ya,xb,yb,xc,yc);
        min=dl1;
        dl2=ras(xa,ya,xb,yb,xd,yd);
        if((dl2<min&&dl2!=-1)||min==-1)min=dl2;
        dl3=ras(xc,yc,xd,yd,xa,ya);
        if((dl3<min&&dl3!=-1)||min==-1)min=dl3;
        dl4=ras(xc,yc,xd,yd,xb,yb);
        if((dl4<min&&dl4!=-1)||min==-1)min=dl4;
        if(min==-1){
            //В случае, если невозможно опустить высоту найдём минимальное расстояние между точками.
            dl1=sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc));
            min=dl1;
            dl2=sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd));
            if(dl2<min)min=dl2;
            dl3=sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc));
            if(dl3<min)min=dl3;
            dl4=sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd));
            if(dl4<min)min=dl4;
        }
    }
    cout<<min;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double ras(double x1, double y1, double x2, double y2, double x3, double y3){

double k,d;

if(x1==x2){ //Если отрезок вертикальный - меняем местами координаты каждой точки.

swap(x1, y1);

swap(x2, y2);

swap(x3, y3);

}

k=(y1-y2)/(x1-x2);//Ищем коэффициенты уравнения прямой, которому принадлежит данный отрезок.

d=y1-k*x1;

double xz=(x3*x2-x3*x1+y2*y3-y1*y3+y1*d-y2*d)/(k*y2-k*y1+x2-x1);

double dl=-1;

if((xz<=x2&&xz>=x1)||(xz<=x1&&xz>=x2)) dl=sqrt((x3-xz)*(x3-xz)+(y3-xz*k-d)*(y3-xz*k-d));//Проверим лежит ли основание высоты на отрезке.

return dl;

}

int main() {

double xa, xb, ya, yb, xc, xd, yc, yd, dl, dl1, dl2, dl3, dl4, min=-1,o,o1,o2,t=-2,s=-2;

cin>>xa>>ya>>xb>>yb>>xc>>yc>>xd>>yd;

o=(xb-xa)*(-yd+yc)-(yb-ya)*(-xd+xc);

o1=(xb-xa)*(yc-ya)-(yb-ya)*(xc-xa);

o2=(-yd+yc)*(xc-xa)-(-xd+xc)*(yc-ya);

if(o!=0){

t=o1/o;

s=o2/o;

}

if((t>=0&&s>=0)&&(t<=1&&s<=1))min=0;//Проверим пересекаются ли отрезки.

else{

//Найдём наименьшую высоту опущенную из конца одного отрезка на другой.

dl1=ras(xa,ya,xb,yb,xc,yc);

min=dl1;

dl2=ras(xa,ya,xb,yb,xd,yd);

if((dl2<min&&dl2!=-1)||min==-1)min=dl2;

dl3=ras(xc,yc,xd,yd,xa,ya);

if((dl3<min&&dl3!=-1)||min==-1)min=dl3;

dl4=ras(xc,yc,xd,yd,xb,yb);

if((dl4<min&&dl4!=-1)||min==-1)min=dl4;

if(min==-1){

//В случае, если невозможно опустить высоту найдём минимальное расстояние между точками.

dl1=sqrt((xa-xc)*(xa-xc)+(ya-yc)*(ya-yc));

min=dl1;

dl2=sqrt((xb-xd)*(xb-xd)+(yb-yd)*(yb-yd));

if(dl2<min)min=dl2;

dl3=sqrt((xb-xc)*(xb-xc)+(yb-yc)*(yb-yc));

if(dl3<min)min=dl3;

dl4=sqrt((xa-xd)*(xa-xd)+(ya-yd)*(ya-yd));

if(dl4<min)min=dl4;

}

cout<<min;

return 0;

}

Решение

Для начала проверим не пересекаются ли отрезки. Пусть для отрезка [latex]AB[/latex] [latex]x=t(x_b-x_a)+x_a[/latex], [latex]y=t(y_b-y_a)+y_a[/latex], а для [latex]CD[/latex] [latex]x=s(x_d-x_c)+x_c[/latex], [latex]y=s(y_d-y_c)+y_c[/latex] (где [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex] ). Если отрезки пересекаются, то выполняются равенства: [latex]t(x_b-x_a)-s(x_d-x_c)=x_c-x_a[/latex] и [latex]t(y_b-y_a)-s(y_d-y_c)=y_c-y_a[/latex]. Полученную систему уравнений решим методом Крамера:
[latex]\Delta =\begin{pmatrix} x_b-x_a & \quad x_c-x_d \\ y_b-y_a & \quad y_c-y_d \end{pmatrix}=(x_b-x_a)(y_c-y_d)-(y_b-y_a)(x_c-x_d)[/latex] [latex]\Delta _1=\begin{pmatrix} x_{ b }-x_{ a } & \quad x_{ c }-x_{ a } \\ y_{ b }-y_{ a } & \quad y_{ c }-y_{ a } \end{pmatrix}=(x_b-x_a)(y_c-y_a)-(y_b-y_a)(x_c-x_a)[/latex] [latex]\Delta _2=\begin{pmatrix} x_{ c }-x_{ a } & \quad x_{ c }-x_{ d } \\ y_{ c }-y_{ a } & \quad y_{ c }-y_{ d } \end{pmatrix}=(y_c-y_d)(x_c-x_a)-(x_c-x_d)(y_c-y_a)[/latex].
Тогда [latex]t=\frac { \Delta_1 }{ \Delta } [/latex], а [latex]s=\frac { \Delta_2 }{ \Delta } [/latex]. Если [latex]0\le t\le 1[/latex], [latex]0\le s\le 1[/latex], а [latex]\Delta \neq 0[/latex], то отрезки пересекаются и расстояние между ними [latex]min[/latex] равно [latex]0[/latex], иначе с каждого конца отрезка попытаемся опустить высоту на противоположный. Если отрезок, на который опускаем высоту вертикальный, то поменяем местами координаты каждого конца отрезка и точки, с которой опускаем высоту (таким образом сохраним расстояние между точкой и отрезком, а отрезок станет горизонтальным). Пусть [latex]k[/latex] и [latex]d[/latex] — коэффициенты уравнения прямой, на которую опущена эта высота. Основание высоты будет находится на прямой в точке [latex]Z[/latex], координаты [latex]Z[/latex] [latex](x_z, y_z)[/latex] можно найти по формуле [latex]y_z=kx_z+d[/latex]. Поскольку высота перпендикулярна отрезку — скалярное произведение их векторов равно [latex]0[/latex]. Тогда [latex](x_2-x_1)(x_3-x_z)+(y_2-y_1)(y_3-y_z)=0[/latex], соответственно [latex]x_z=\frac { x_3x_2-x_3x_1+y_2y_3-y_1y_3+y_1d-y_2d }{ ky_2-ky_1+x_2-x_1 } [/latex] (где [latex](x_3, y_3)[/latex] — координаты точки, с которой была опущена высота, [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex] — координаты концов отрезка, принадлежащего прямой на которую опущена высота). Вычислим длину [latex]dl[/latex] каждой высоты, основание которой принадлежит одному из данных отрезков: [latex]dl=\sqrt { {(x_3-x_z)}^{2}+{(y_3-x_zk-d)}^{2} }[/latex](где [latex] (x_3, y_3)[/latex] — координаты точки, с которой была опущена высота). Минимальная длина высоты и будет наименьшим расстоянием между отрезками. В случае, если невозможно опустить высоты из одного отрезка на другой: расстояние между ними будет равно минимальному расстоянию между концами двух отрезков [latex]min=\sqrt { {( x_1-x_3) }^{ 2 }+{ (y_1-y_3) }^{ 2 } }[/latex] (где [latex](x_1, y_1)[/latex] — координаты одного из концов первого отрезка, а [latex](x_3, y_3)[/latex] — координаты одного из концов второго отрезка) .

Ссылки

Код программы
Условие задачи (страница 32).

Related Images:

Mif 11

15/09/2016 by Станислав Коциевский

Задача

Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин на плоскости.

Тесты

Входные данные	Результат работы программы
1 1 1 7 5 3 1 6	0
5 6 8 8 2 2 5 4	2
1 -1 1 -3 2 -2 4 -1	1
-5 -1 -5 -3 -2 -1 -3 -2	2
-1 1 -1 3 -4 2 -3 5	2.52982
1 4 3 6 3 4 5 4	1.41421

Код программы

#include <iostream>
#include <cmath>
using namespace std;

struct point //точка
{
    double x;
    double y;
};
struct straight //прямая в виде общего уравнения Ax + By + C = 0
{
    double A;
    double B;
    double C;
};
straight create_straight (point A, point B)
{
    straight s;
    s.A = A.y - B.y;
    s.B = B.x - A.x;
    s.C = A.x * B.y - B.x * A.y;
    return s;
}
double r (point A, point B) //расстояние между двумя точками
{
    return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));
}
point projection (point A, point B, point C) // проекция точки С на прямую AB
{
    double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB
    double y = A.x - B.x;
    double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));
    point H;
    H.x = C.x + x * L;
    H.y = C.y + y * L;
    return H;
}
point intersection (straight a, straight b) //точка пересечения прямых a и b
{
    point ans;
    ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);
    ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);
    return ans;
}
void check_projection (point A, point B, point C, double & min_dis)
{
    point H = projection(A,B,C);
    if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку
    {
        if (r(H,C) < min_dis)
        {
            min_dis = r(H,C);
        }
    }
}
double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются
{
    double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));
    check_projection (A,B,C,min_dis);
    check_projection (A,B,D,min_dis);
    check_projection (C,D,A,min_dis);
    check_projection (C,D,B,min_dis);
    return min_dis;
}
int main()
{
    point A,B,C,D;
    cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;
    straight AB = create_straight(A,B);
    straight CD = create_straight(C,D);
    if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых
    {
        cout<<distance_if_not_intersect(A,B,C,D);
    }
    else
    {
        point H = intersection(AB,CD);
        if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам
        (H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )
        {
            cout<<0;
        }
        else
        {
            cout<<distance_if_not_intersect(A,B,C,D);
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

struct point //точка

{

double x;

double y;

};

struct straight //прямая в виде общего уравнения Ax + By + C = 0

{

double A;

double B;

double C;

};

straight create_straight (point A, point B)

{

straight s;

s.A = A.y - B.y;

s.B = B.x - A.x;

s.C = A.x * B.y - B.x * A.y;

return s;

}

double r (point A, point B) //расстояние между двумя точками

{

return sqrt((A.x - B.x)*(A.x - B.x)+(A.y - B.y)*(A.y - B.y));

}

point projection (point A, point B, point C) // проекция точки С на прямую AB

{

double x = B.y - A.y; //x и y - координаты вектора, перпендикулярного к AB

double y = A.x - B.x;

double L = (A.x*B.y - B.x*A.y + A.y*C.x - B.y*C.x + B.x*C.y - A.x*C.y)/(x*(B.y - A.y) + y*(A.x - B.x));

point H;

H.x = C.x + x * L;

H.y = C.y + y * L;

return H;

}

point intersection (straight a, straight b) //точка пересечения прямых a и b

{

point ans;

ans.x = (b.C*a.B - a.C*b.B)/(a.A*b.B - b.A*a.B);

ans.y = (a.C*b.A - b.C*a.A)/(b.B*a.A - a.B*b.A);

return ans;

}

void check_projection (point A, point B, point C, double & min_dis)

{

point H = projection(A,B,C);

if ((H.x >= min(A.x,B.x) && H.x <= max(A.x,B.x)) && (H.y >= min(A.y,B.y) && H.y <= max(A.y,B.y))) //проекция принадлежит отрезку

{

if (r(H,C) < min_dis)

{

min_dis = r(H,C);

}

double distance_if_not_intersect (point A, point B, point C, point D) //расстояние между отрезками, если они не пересекаются

{

double min_dis = min(min(r(A,C),r(A,D)),min(r(B,C),r(B,D)));

check_projection (A,B,C,min_dis);

check_projection (A,B,D,min_dis);

check_projection (C,D,A,min_dis);

check_projection (C,D,B,min_dis);

return min_dis;

}

int main()

{

point A,B,C,D;

cin>>A.x>>A.y>>B.x>>B.y>>C.x>>C.y>>D.x>>D.y;

straight AB = create_straight(A,B);

straight CD = create_straight(C,D);

if (AB.A/CD.A == AB.B/CD.B) //условие параллельности прямых

{

cout<<distance_if_not_intersect(A,B,C,D);

}

else

{

point H = intersection(AB,CD);

if ( (H.x >= min(A.x, B.x) && H.x <= max(A.x,B.x) && H.x >= min(C.x, D.x) && H.x <= max(C.x,D.x)) && //точка пересечения принадлежит обоим отрезкам

(H.y >= min(A.y, B.y) && H.y <= max(A.y,B.y) && H.y >= min(C.y, D.y) && H.y <= max(C.y,D.y)) )

{

cout<<0;

}

else

{

cout<<distance_if_not_intersect(A,B,C,D);

}

return 0;

}

Решение

Основная идея состоит в том, что расстояние между непересекающимися отрезками [latex]AB[/latex] и [latex]CD[/latex] — это минимальная из длин, соединяющих вершины разных отрезков, и длин перпендикуляров, проведенных из вершины на противоположный отрезок. Подробнее о математической части поиска перпендикуляра тут. Кроме этого, отрезки могут пересекаться, что проверяется отдельно. В таком случае, расстояние между ними равно нулю.

Чтобы проверить, пересекаются ли отрезки, нужно сначала проверить, не параллельны ли они.Если они не параллельны, нужно найти точку пересечения прямых, на которых лежат отрезки, а затем проверить принадлежит ли она обоим отрезкам. Отрезки пересекаются тогда и только тогда, когда они лежат на пересекающихся прямых, точка пересечения которых принадлежит обоим отрезкам. Координаты точки пересечения находятся из системы уравнений прямых, на которых лежат отрезки.
[latex] \begin{cases} A_{1}x + B_{1}y + C_{1} = 0 \\ A_{2}x + B_{2}y + C_{2} = 0 \end{cases} [/latex]

Из первого уравнения: [latex]x = \frac{-B_{1}y-C_{1}}{A_{1}}[/latex]

Подставим [latex]x[/latex] во второе уравнение:

[latex] \frac{A_{2}}{A_{1}}(-B_{1}y-C_{1}) + B_{2}y + C_{2} = 0[/latex] [latex](*)[/latex]

Решив уравнение [latex](*)[/latex] получим:

[latex]y = \frac{C_{1}A_{2}-C_{2}A_{1}}{A_{1}B_{2}-A_{2}B_{1}}[/latex].

Тогда

[latex]x = \frac{C_{2}B_{1}-C_{1}B_{2}}{A_{1}B_{2}-A_{2}B_{1}}[/latex]

Ссылка на код на ideone

Related Images:

Mif 15

26/10/2015 by Женя Максимова

Задача. Вычислить расстояние между двумя отрезками [latex]AB[/latex] и [latex]CD[/latex], заданных координатами вершин в четырехмерном пространстве.

Тесты

(1)

№	[latex]A_0[/latex]	[latex]A_1 [/latex]	[latex]A_2[/latex]	[latex]A_3[/latex]	[latex]B_0[/latex]	[latex]B_1[/latex]	[latex]B_2[/latex]	[latex]B_3[/latex]
1	1	0	0	0	2	0	0	0
2	1	0	0	0	3	0	0	0
3	-1	1	0	6	-2	-1	1	6
4	1	1	1	1	2	2	2	2
5	1	1	1	2	8	5	7	10
6	1	1	0	0	1	0	1	1
7	3	4	7	8	9	5	6	2
8	1	2	2	3	1	4	8	9

(2)

№	[latex]C_0[/latex]	[latex]C_1[/latex]	[latex]C_2[/latex]	[latex]C_3[/latex]	[latex]D_0[/latex]	[latex]D_1[/latex]	[latex]D_2[/latex]	[latex]D_3[/latex]	[latex]r[/latex]
1	1	1	0	0	2	1	0	0	1.000000
2	2	4	0	0	2	4	3	0	4.000000
3	-1	-1	0	6	2	1	1	6	1.154701
4	-9	-9	-9	-9	-5	-5	-5	-5	12.000000
5	8	0	0	0	2	1	1	1	1.414214
6	2	3	2	0	1	4	9	1	3.000000
7	7	4	11	15	15	5	12	9	9.000000
8	5	7	2	23	4	8	8	21	13.000000

Код программы

#include "stdio.h"
#include <cmath>

double dot(double * u, double * v);
double abs(double * u);
double min(double a, double b, double c, double d);
void prod(double k, double * u, double * v);
void diff(double * a, double * b, double * c);
void summ(double * a, double * b, double * c);
bool in(double s);
bool in(double s, double t);
double sd(double s, double t);
double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];
double u[4],v[4],w0[4];

double InterSegmentDistance4d()
//input: four 4d points P0, P1, Q0, Q1
// output: r = minimal distance between lines segments P0P1 and Q0Q1
    {
        double r = 0;
        //calculation of three vectors
        //u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0
        diff(P1, P0, u);  diff(Q1, Q0, v);  diff(Q0, P0, w0);
        //calculation of supporting scalar variables
        //a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v
        double  a, b, c, d, e;
        a = dot(u,u);  // a=u^2;
        b = dot(u,v);         
        c = dot(v,v);  // c=v^2;
        d = dot(u,w0);
        e = dot(v,w0);
        //calculation of main determinant
        // D = b^2 - a*c
        double D = b*b - a*c;
        if (D == 0) //lines are parallel
            {
                double t0=-e/c; 
                double t1=-e/c; 
                double s0 = (-e+b)/c ; 
                double s1= (e-c)*b/(c*a);
                if (in(t0) || in(t1) || in(s0) || in(s1))
                    {
                        double wq[4];
                        prod(e/c,v,  wq);  //projection w0 on line q
                        double wd[4];
                         diff(w0,wq,  wd);
                          r = abs(wd);
                           return r ; //r = |w0 - wq|
                    }
                //else minimal distance between segments equals minimal distance between ends of segments
                        r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));
                         return r;   
            }
        // else lines are not parallel
            {
                //calculation of determinants
                double D1 = b*e - c*d,  D2 = a*e - b*d;
                //calculation of parameters for minimal segment between lines
                double sc = D1/D, tc = D2/D;
                if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines
                    {
                        return r = sd(sc,tc); // r = |wc|
                    }
                //else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]
                    {
                        double t1 = 0,   s1=_(d/a);
                        double t2 = _(-2*e/c), s2=0;
                        double t3 = 1,   s3=_(2*(b+d)/a);
                        double t4 = _(2*(b+e)/c), s4=0;
                         return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4)); 
                    }
            }
    }

int main()
    {
        scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);
        scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);
        scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);
        scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);
         printf("%lf\n", InterSegmentDistance4d());
          return 0;
    }

double dot(double * u, double * v)//scalar production of two vectors
    {
        return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];
    }

double abs(double * u)//length of vector
    {
        return sqrt(dot(u,u));
    }

double min(double a, double b, double c, double d)//minimal from four values
    {
        double m = a;
        if(m>b) m = b;
         if(m>c) m = c;
          if(m>d) m = d;
           return m;
    }

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)
    {
        c[0]=a[0]-b[0];
        c[1]=a[1]-b[1];
        c[2]=a[2]-b[2];
        c[3]=a[3]-b[3];
    }

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)
    {
        c[0]=a[0]+b[0];
        c[1]=a[1]+b[1];
        c[2]=a[2]+b[2];
        c[3]=a[3]+b[3];
    }

void prod(double k, double * u, double * v)//production of number and vector
    {
        v[0] = k * u[0];
        v[1] = k * u[1];
        v[2] = k * u[2];
        v[3] = k * u[3];
    }

bool in(double s)//checking if the vatue is in [0,1]
    {
        return 0 <= s && s <= 1 ;
    }

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]
    {
        return  in(t) && in(s);
    }

double sd(double s, double t)//distance between two points defined by two parameters s and t
    {
        double Pc[4], Qc[4], W[4];
        prod(s,u, Pc);
        prod(t,v, Qc);
         summ(Pc,P0, Pc);
         summ(Qc,Q0, Qc);
          diff(Qc, Pc, W);
           return  abs(W);
    }

double _(double s)//restrict a value s on the interval [0,1]
    {
        double s1 = s;
        if(s > 1)s1 = 1;
        if(s < 0)s1 = 0;
         return s1;
    }

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include "stdio.h"

#include <cmath>

double dot(double * u, double * v);

double abs(double * u);

double min(double a, double b, double c, double d);

void prod(double k, double * u, double * v);

void diff(double * a, double * b, double * c);

void summ(double * a, double * b, double * c);

bool in(double s);

bool in(double s, double t);

double sd(double s, double t);

double _(double s);

double P0[4],P1[4],Q0[4],Q1[4];

double u[4],v[4],w0[4];

double InterSegmentDistance4d()

//input: four 4d points P0, P1, Q0, Q1

// output: r = minimal distance between lines segments P0P1 and Q0Q1

{

double r = 0;

//calculation of three vectors

//u = P1 - P0, v = Q1 - Q0, w0 = Q0 - P0

diff(P1, P0, u); diff(Q1, Q0, v); diff(Q0, P0, w0);

//calculation of supporting scalar variables

//a = u*u, b = u*v, c = v*v, d = w0*u, e = w0*v

double a, b, c, d, e;

a = dot(u,u); // a=u^2;

b = dot(u,v);

c = dot(v,v); // c=v^2;

d = dot(u,w0);

e = dot(v,w0);

//calculation of main determinant

// D = b^2 - a*c

double D = b*b - a*c;

if (D == 0) //lines are parallel

{

double t0=-e/c;

double t1=-e/c;

double s0 = (-e+b)/c ;

double s1= (e-c)*b/(c*a);

if (in(t0) || in(t1) || in(s0) || in(s1))

{

double wq[4];

prod(e/c,v, wq); //projection w0 on line q

double wd[4];

diff(w0,wq, wd);

r = abs(wd);

return r ; //r = |w0 - wq|

}

//else minimal distance between segments equals minimal distance between ends of segments

r = min(sd(0,0), sd(0,1), sd(1,0), sd(1,1));

return r;

}

// else lines are not parallel

{

//calculation of determinants

double D1 = b*e - c*d, D2 = a*e - b*d;

//calculation of parameters for minimal segment between lines

double sc = D1/D, tc = D2/D;

if(in(sc,tc)) //minimal distance between segments equals minimal distance between lines

{

return r = sd(sc,tc); // r = |wc|

}

//else minimal segment is defined by some parameter point (s,t) on edge of square [0,1]x[0,1]

{

double t1 = 0, s1=_(d/a);

double t2 = _(-2*e/c), s2=0;

double t3 = 1, s3=_(2*(b+d)/a);

double t4 = _(2*(b+e)/c), s4=0;

return min(sd(s1,t1), sd(s2,t2),sd(s3,t3), sd(s4,t4));

}

int main()

{

scanf("%lf %lf %lf %lf",&P0[0], &P0[1], &P0[2],&P0[3]);

scanf("%lf %lf %lf %lf",&P1[0], &P1[1], &P1[2],&P1[3]);

scanf("%lf %lf %lf %lf",&Q0[0], &Q0[1], &Q0[2],&Q0[3]);

scanf("%lf %lf %lf %lf",&Q1[0], &Q1[1], &Q1[2],&Q1[3]);

printf("%lf\n", InterSegmentDistance4d());

return 0;

}

double dot(double * u, double * v)//scalar production of two vectors

{

return u[0]*v[0]+u[1]*v[1]+u[2]*v[2]+u[3]*v[3];

}

double abs(double * u)//length of vector

{

return sqrt(dot(u,u));

}

double min(double a, double b, double c, double d)//minimal from four values

{

double m = a;

if(m>b) m = b;

if(m>c) m = c;

if(m>d) m = d;

return m;

}

void diff(double * a, double * b, double * c)//difference of two 4d objects(points or vectors)

{

c[0]=a[0]-b[0];

c[1]=a[1]-b[1];

c[2]=a[2]-b[2];

c[3]=a[3]-b[3];

}

void summ(double * a, double * b, double * c)//sum of two 4d objects(points or vecrors)

{

c[0]=a[0]+b[0];

c[1]=a[1]+b[1];

c[2]=a[2]+b[2];

c[3]=a[3]+b[3];

}

void prod(double k, double * u, double * v)//production of number and vector

{

v[0] = k * u[0];

v[1] = k * u[1];

v[2] = k * u[2];

v[3] = k * u[3];

}

bool in(double s)//checking if the vatue is in [0,1]

{

return 0 <= s && s <= 1 ;

}

bool in(double s, double t)//checking if the value is in [0,1]x[0,1]

{

return in(t) && in(s);

}

double sd(double s, double t)//distance between two points defined by two parameters s and t

{

double Pc[4], Qc[4], W[4];

prod(s,u, Pc);

prod(t,v, Qc);

summ(Pc,P0, Pc);

summ(Qc,Q0, Qc);

diff(Qc, Pc, W);

return abs(W);

}

double _(double s)//restrict a value s on the interval [0,1]

{

double s1 = s;

if(s > 1)s1 = 1;

if(s < 0)s1 = 0;

return s1;

}

Алгоритм и его обоснование

Расстояние между отрезками в четырехмерном пространстве находится по-разному, в зависимости от взаимного расположения этих отрезков. Тут мы можем выделить два основных случая:

Отрезки лежат на параллельных прямых или на одной прямой.
Отрезки лежат на пересекающихся либо на скрещивающихся прямых.

Чтобы выяснить, с каким случаем мы имеем дело, рассмотрим общую картину взаимного расположения отрезков и опишем ее математически:

По условию нам заданы 4 точки: [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] — концы двух отрезков. Для удобства представления уравнений и точек, связанных с ними, обозначим их [latex]P_0[/latex], [latex]P_1[/latex], [latex]Q_0[/latex] и [latex]Q_1[/latex] соответственно. Через эти пары точек мы можем провести 2 прямые [latex]p[/latex] и [latex]q[/latex], параметрические уравнения которых имеют вид:

[latex]

\begin{matrix}
\vec p = P_0 + \vec u \cdot s \\
\vec q = Q_0 + \vec v \cdot t
\end{matrix}

[/latex],

где векторы:

[latex]

\begin{matrix}

\vec u = P_1 — P_0\\

\vec v = Q_1 — Q_0

\end{matrix}

[/latex],

а [latex]s[/latex] и [latex]t[/latex] — параметры. При [latex]s=0[/latex] или [latex] t=0[/latex] мы получаем начальную точку соответствующего отрезка, а при [latex]s=1[/latex] или [latex]t=1[/latex] — конечную. При произвольном значении параметра мы получаем произвольную точку на прямой.

Рассмотрим вектор [latex]\vec w = Q — P[/latex] , соединяющий 2 произвольные точки на этих прямых. Легко показать, что вектор [latex]\vec w[/latex] соединяет 2 ближайшие точки [latex]Q_c[/latex] и [latex]P_c[/latex] при условии:

[latex]\vec w \perp p[/latex] и [latex]\vec w \perp q[/latex].

Этому условию соответствует система из двух уравнений:

[latex] \begin{cases}
\vec u \cdot \vec w = 0\\
\vec v \cdot \vec w = 0
\end{cases}

[/latex]

Распишем ее для [latex]\vec w = Q_0 — P_0 + \vec v \cdot t — \vec u \cdot s = \vec w_0 + \vec v \cdot t — \vec u \cdot s[/latex] :
[latex]

\begin{cases}
\vec u \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0\\
\vec v \cdot ( \vec w_0 + \vec v \cdot t — \vec u \cdot s ) = 0
\end{cases}

[/latex]

Введем вспомогательные скалярные переменные:
[latex]

\begin{matrix}

a&=&\vec u \cdot \vec u\\
b&=&\vec u \cdot \vec v\\
c&=&\vec v \cdot \vec v\\
d&=&\vec u \cdot \vec w_0\\
e&=&\vec v \cdot \vec w_0

\end{matrix}

[/latex]

Теперь наша система будет выглядеть так:

[latex]

\begin{cases}
d — a \cdot s + b \cdot t = 0 \\
e — b \cdot s + c \cdot t = 0
\end{cases}
[/latex]

Перепишем систему в удобном для нас виде:

[latex] \begin{cases}
a \cdot s — b \cdot t = d \\
b \cdot s — c \cdot t = e
\end{cases}
[/latex]

Решение этой системы мы можем получить, например, методом Крамера.

Главный определитель системы: [latex]D = b^2 — a \cdot c[/latex]

Два вспомогательных определителя:
[latex] \begin{matrix}
D_1 = b \cdot e — c \cdot d\\
D_2 = a \cdot e — b \cdot d\\
\end{matrix}
[/latex] Если [latex]D \neq 0[/latex], то существует единственное решение:

[latex]

\begin{cases}
s_c = \frac{D_1}{D} \\
t_c = \frac{D_2}{D}
\end{cases}
[/latex]

Если же мы получаем [latex]D = 0[/latex], легко показать, что отрезки параллельны. То есть мы имеем дело со случаем 1.

Тогда:

а) Если хотя бы одна точка одного отрезка проецируется на другой отрезок, то расстояние между отрезками равняется расстоянию между прямыми.

Найдем проекцию точки [latex]P_0[/latex] на линию [latex]q[/latex]. Для этого сначала найдем вектор, который является проекцией вектора [latex]\vec w_0[/latex] на линию [latex]q[/latex].

[latex]\vec w_q=(\vec w_0 \cdot \vec v) \cdot \frac{\vec v}{v^2}[/latex].
Конец полученного вектора находится в точке [latex]Q_0[/latex], а начало в новой точке [latex]P_{0q}=Q_0-\vec w_q[/latex]. Соединим точки [latex]P_0[/latex] и [latex]P_{0q}[/latex] вектором [latex]\vec w_p = P_{0q} — P_0[/latex]. Длина полученного вектора и будет искомым расстоянием: [latex]r = \left| P_0 P_{0q} \right|[/latex].

Для проверки условия а) необходимо получить проекции остальных исходных точек на отрезки:
[latex] \begin{matrix}
P_{1q} = P_{0q} + \vec u\\
Q_{0p} = P_0 + \vec w_q\\
Q_{1p} = Q_{0p} + \vec v
\end{matrix}
[/latex]

Если точка [latex]P_{0q}[/latex] лежит на прямой [latex]q[/latex], задаваемой уравнением:
[latex]\vec q = Q_0 + \vec v \cdot t[/latex],
то определить, принадлежит ли точка [latex]P_{0q}[/latex] отрезку [latex]Q_0 Q_1[/latex] можно, решив уравнение:
[latex]P_{0q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q + \vec v \cdot t[/latex].
Домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение: [latex] 0 = e + c \cdot t[/latex], отсюда [latex]t = \frac{-e}{c}[/latex].

Если [latex]t \in \left[0,1\right][/latex], то точка [latex]P_{0q}[/latex] лежит на отрезке [latex]Q_0 Q_1[/latex]. Если же нет, переходим к аналогичной проверке следующих точек:

[latex]P_{1q}:[/latex] [latex]P_{1q} = Q_0 + \vec v \cdot t[/latex].
[latex] 0 = \vec w_q — \vec u + \vec v \cdot t[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec v[/latex], мы получим уравнение:

[latex] 0 = e — b + c \cdot t[/latex],
отсюда [latex]t = \frac{-e+b}{c}[/latex].
[latex]Q_{0p}:[/latex] [latex]Q_{0p} = P_0 + \vec u \cdot s[/latex].
[latex]0 =-\vec w_q + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} + a \cdot s[/latex],
отсюда [latex]s = \frac{e \cdot b}{c \cdot a}[/latex].
[latex]Q_{1p}:[/latex] [latex]Q_{1p} = P_0 + \vec u \cdot s[/latex].
[latex] 0 = -\vec w_q — \vec v + \vec u \cdot s[/latex].
Опять домножив обе части скалярно на вектор [latex]\vec u[/latex], мы получим уравнение:

[latex] 0 = -\frac{e \cdot b}{c} — b + a \cdot s[/latex],
отсюда [latex]s = \frac{(e — c) \cdot b}{c \cdot a}[/latex].
б) В противном случае, расстояние между отрезками равняется минимальному расстоянию между их концами. Здесь задача предельно упрощается. Мы находим длины отрезков, попарно соединяющих 4 исходные точки, и выбираем наименьший из них.

Если же исходные отрезки лежат на пересекающихся либо на скрещивающихся прямых, мы также рассматриваем 2 случая:

а) Оба конца кратчайшего отрезка, соединяющего прямые, лежат на соответствующих исходных отрезках:
[latex]P_c \in P_0 P_1[/latex] и [latex]Q_c \in Q_0 Q_1[/latex].

В этом случае пара параметров [latex](s_c, \; t_c)[/latex] принадлежит области: [latex](s,t):\left[0,1\right]\times \left[0,1\right].[/latex]

То есть, решение тривиально: ответом будет дина вектора [latex]\vec w_c[/latex]

б) Хотя бы один из концов кратчайшего отрезка, соединяющего прямые, не лежит на исходном отрезке, то есть:
[latex]P_c \not\in P_0 P_1[/latex] или [latex]Q_c \not\in Q_0 Q_1[/latex],
что соответствует значениям параметров [latex]s_c \not\in \left[0,1\right][/latex] или [latex]t_c \not\in \left[0,1\right][/latex].

В этом случае минимальное расстояние между отрезками определяется на границе области: [latex](s,t):\left[0,1\right]\times \left[0,1\right][/latex] (см. рисунок ниже):

Здесь решением является длина кратчайшего отрезка.

Длину отрезка, соединяющего 2 прямые, можно оценивать по квадрату длины вектора [latex]\vec v[/latex]: [latex]w^2=(\vec w)^2=(\vec w_0 — \vec u \cdot s + \vec v \cdot t)^2[/latex].

В частности, минимум [latex]w^2[/latex] достигается в точке [latex](s_c,t_c)[/latex].
Однако в случае б) мы должны найти минимум расстояния на границе нашей области, то есть решить задачу нахождения минимума при ограничениях (решить задачу условной минимизации). В нашем случае ограничения имеют очень простой вид — оси координат, и две линии, параллельные им. Поэтому мы можем решить на четырех границах 4 упрощенные задачи минимизации, а затем выбрать наименьшее решение.

Замечание: В пространстве параметров функция [latex]w^2(s,t)[/latex] представляет из себя эллиптический параболоид. Однако для простоты мы выше изобразили его линии уровня в виде окружностей. Типичный вид эллиптического параболоида и его линий уровня представлен на рисунках ниже:

Рассмотрим поочередно все 4 ограничения и решим задачу для них:

(1) Пусть [latex]t=t_1=0[/latex].

Тогда: [latex]{w^2\mid_{t_1=0}} = (\vec w_0-\vec u \cdot s_1)^2[/latex].

Для определения экстремума приравняем производную к нулю:[latex] \begin{array}{r}
\frac{d}{ds_1}{(\vec w_0-\vec u \cdot s_1)^2}=0\\
2 \cdot (\vec w_0-\vec u \cdot s_1) \cdot (- \vec u)=0\\
-d +a \cdot s_1=0\\
s_1=\frac{d}{a}
\end{array}
[/latex]

Легко показать, что при [latex]s_1>1[/latex] мы должны присвоить ему значение [latex]s_1=1[/latex], а если [latex]s<0[/latex] — значение [latex]s_1=0[/latex], так как мы не должны выходить за границы исходных отрезков.

Подставим полученное значение [latex]s[/latex] в уравнение прямой [latex]p[/latex] для точки [latex]P_c[/latex]:[latex]P_c = P_0 + \vec u \cdot s.[/latex]

А точка [latex]Q_c[/latex] совпадает с точкой [latex]Q_0[/latex]. Тогда первый минимум равен: [latex]r_1 = Q_0 P_c[/latex].

Аналогично найдем три остальных минимума [latex]r_2, r_3, r_4[/latex], приравняв [latex]s[/latex] к нулю, а затем [latex]t[/latex] и [latex]s[/latex] к единице. Наименьший из них и есть искомое расстояние [latex]r[/latex].

Код программы

Related Images:

Ю2.15

01/10/2015 by Таран Таня

Задача. Общая точка

Два отрезка на плоскости заданы координатами своих концов. Определить имеют ли эти отрезки общие точки.

Замечание. Необходимо рассмотреть различные случаи взаимной ориентации отрезков: на одной прямой, на параллельных или пересекающихся прямых. Тестирование должно предусмотреть все такие ситуации.

Входные данные

Координаты концов двух отрезков [latex]AB, CD [/latex] в формате [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex] ([latex]x_i, y_i[/latex] — действительные числа).

Выходные данные

Расположение отрезков, а именно:

«Intersect at point [latex](x, y)[/latex]»
«Don’t intersect»
«Paralell»
«On the same line, but don’t intersect»
«Overlap» (Находятся на одной прямой и хотя бы одна из точек совпадает)

Тесты

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 5 4 1 3 5 3	Intersect at point (3.66667, 3)
-7 2 -4 2 -6 3 -3 3	Paralell
1 2 3 2 2 2 6 2	Overlap
1 2 4 2 5 2 7 2	On the same line, but don’t intersect
1 2 4 4 2 1 5 3	Paralell
1 1 4 2 7 3 10 4	On the same line, but don’t intersect
1 1 5 3 5 3 7 4	Overlap
1 1 5 4 1 4 5 2	Intersect at point (3.4, 2.8)
1 1 2 4 3 2 6 4	Don’t intersect

Координаты [latex] A(x_1, y_1) B(x_2, y_2) C (x_3, y_3) D(x_4, y_4)[/latex]	Расположение отрезков
1 1 1 5 3 2 3 4	Paralell
1 2 4 5 2 2 2 5	Intersect at point (2, 3)
2 1 2 2 2 4 2 6	On the same line, but don’t intersect
2 1 2 5 1 2 4 2	Intersect at point (2, 2)
1 2 4 2 2 3 2 5	Don’t intersect

Алгоритм решения

Представленный в данной программе алгоритм достаточно объемный и содержит в себе большое количество вариантов поведения программы, поэтому разбирать его будем постепенно.
Начнем с функций, которые понадобятся в дальнейшем ходе решения:

areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
( Основная формула: [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
getMin — возвращает минимум двух чисел.
getMax — возвращает максимум двух чисел.
projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
( Основная формула: [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
( Основная формула: [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
getCos — функция, принимающая координаты двух векторов и возвращающая косинус угла между ними.
( Основная формула: [latex]\frac{x_1x_2 + y_1y_2}{\sqrt(x_1^2 + y_1^2) + \sqrt(x_2^2 + y_2^2)}[/latex] )

Перейдем к основной части программы. Сразу следует оговорить, что последующее решение будет базироваться на векторах и работе с уравнением прямой вида [latex] y = kx + b [/latex], поэтому для удобства отдельно заведем переменные для координат векторов соответствующих отрезкам и значений вычисленных коэффициентов и свободных членов уравнений прямых. Одной из главных проблем на пути решения стали отрезки располагающиеся на прямых вида [latex]x = a [/latex], ведь если обратится к пунктам 5, 6 можно заметить, что в таких случаях мы получим исключение из-за деления на ноль. Этим вызвано вынужденное разделение программы на два блока — где ни один из отрезков не располагается параллельно оси ординат и когда хотя бы один из них параллелен. Это удается достичь благодаря инициализации логических переменных, принимающих значение true, когда отрезок расположен на прямой [latex]x = a[/latex]. Также изначально подсчитываем значения переменных yIntercept1, yIntercept2, slope1, slope2 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

Теперь мы можем приступить к общему рассмотрению сложившейся ситуации, когда прямые параллельные оси ординат отсутствуют:

Решим систему уравнений для двух заданных прямых и таким образом найдем точку их пересечения.
[latex] \left\{\begin{matrix}
k_1x + b_1 = y & \\
k_2x + b_2 = y &
\end{matrix}\right.[/latex]
Найдя точку с координатами [latex](xIntersection,yIntersection)[/latex], следующим шагом станет проверка : принадлежит ли найденная точка имеющимся отрезкам. Для этого воспользуемся формулой скалярного произведения и определим косинус угла между векторами с началом в точке [latex](xIntersection, yIntersection)[/latex] и концами в соответствующих концах отрезка. Выполняем ее для двух отрезков. Если в обоих случаях найденный косинус будет [latex] \le[/latex] [latex]0[/latex], то точка находится на двух отрезках одновременно и является их пересечением. Выводим сообщение «Intersect at point [latex](xIntersection, yIntersection)[/latex]«.
В случае, если такая точка не найдена в следствие определенных причин, рассмотрим следующие возможные ситуации:
а) При условии, что равны свободные члены уравнения прямых и точка не была найдена, можем проверить утверждение, что рассматриваемые прямые совпадают, а заданные отрезки находятся на ней. Здесь требуют рассмотрения два варианта: отрезки накладываются, если проекции отрезков на ось абсцисс накладываются друг на друга, или же отрезки находятся на одной прямой и не пересекаются. Выводим соответствующее сообщение : «Overlap»/»On the same line, but don’t intersect».
б) Если свободные члены не равны и не выполнилось ни одно из предыдущих утверждений, приходим к выводу, что возможно отрезки, которые задают вектора, параллельны. Выполняем проверку на коллинеарность , в случае подтверждения предположения выводим сообщение : «Parallel».
в) Пройдя через все вышеупомянутые проверки и не получив логического значения true, определяем, что данные отрезки не пересекаются и не удовлетворяют ни одному из особенных случаев. Выводим сообщение : «Don’t intersect».Таким образом рассмотрение общего случая окончено. Перейдем ко второй ситуации:

Если оба отрезка расположены на прямых вида [latex]x = a[/latex], то имеем следующие варианты:
а) Если отрезки расположены на одной прямой и их проекции на ось ординат пересекаются, выводим сообщение : «Overlap».
б) Если отрезки расположены на одной прямой и их проекции на ось ординат не пересекаются, выводим сообщение : «On the same line, but don’t intersect».
в) Если отрезки расположены не на одной прямой, выводим сообщение «Paralell».
При условии, что только одна из прямых имеет вид [latex]x = a[/latex], рассмотрим следующие ситуации:
а)Только одна из прямых имеет вид [latex]x = a[/latex] и обе имеют коэффициент угла наклона равный [latex]0[/latex]. Перед нами две прямые вида: [latex] y = b[/latex] и [latex]x = a [/latex]. Выполняем смену между соответствующими координатами, чтобы не дублировать код для двух аналогичных ситуаций и рассматриваем только одну из них. Нетрудно заметить, что единственным решением является точка [latex](x_3/x_4, y_1/y_2)[/latex] . Используя метод getCos, выполняем уже описанную выше проверку на принадлежность точки отрезку. Если да — выводим сообщение : «Intersect at point [latex](x_3, y_1)[/latex]», в противном случае : «Don’t intersect».
б) Однако, ни одна из предыдущих проверок могла не выполниться, так как существует еще одно расположение отрезков на прямых [latex] y = kx + b [/latex] и [latex]x = a [/latex]. Выполняем аналогичную операцию по смене координат во избежание дублирования кода. Единственным решением данной системы может являться точка [latex](x3/x4 + yIntercept1, x3/x4)[/latex]. Повторяем операции аналогичные последним из пункта б). Выводим сообщение: «Intersect at point [latex](x3 + yIntercept1, x3)[/latex]» или «Don’t intersect».
(В последних двух пунктах несколько раз координаты были записаны через черту, что , вероятно, требует пояснения: в этих ситуациях наблюдалось равенство и какую координату мы выберем не существенно).

Код программы:

#include <iostream>
#include <math.h>
using namespace std;

bool areCollinear(double x1, double y1, double x2, double y2) {
	return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность
}

double getMin(double x1, double x2) {
	return x1 < x2 ? x1 : x2;
}

double getMax(double x1, double x2) {
	return x1 > x2 ? x1 : x2;
}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций
bool projectionsIntersect(double x1, double x2, double x3, double x4) {
	return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));
}

// Вычисление коэффициента угла наклона уравнения прямой
double getSlope(double x1, double  y1, double x2, double y2) {
	return (y2 - y1) / (x2 - x1); 
}

// Вычисление свободного члена уравнения прямой
double getYIntercept(double x1, double  y1, double x2, double y2) {
	return (x2 * y1 - x1 * y2) / (x2 - x1);
}

// Нахождение косинуса угла между векторами
double getCos(double x1, double  y1, double x2, double y2) {
	return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));
}

int main() {
    double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки
	bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a 
	double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки
	double xIntersection, yIntersection; // Координаты точки пересечения, если она существует
	double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков 
	cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;
	double vx1 = x2 - x1;
	double vy1 = y2 - y1; // Вычислим координаты векторов,
	double vx2 = x4 - x3; // Задаваемых данными отрезками
	double vy2 = y4 - y3;
	slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a
	slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона
	vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a 
    vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true
	if (!f1 && !f2) {
		xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений 
		yIntersection = slope1 * xIntersection + yIntercept1;
		if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках 
	        cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")"; 
	    else if (yIntercept1 == yIntercept2) {
    		if (projectionsIntersect(x1, x2, x3, x4))
        		cout << "Overlap";
            else 
		        cout << "On the same line, but don't intersect";
        } 
        else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4))) 
            cout << "Paralell";
	    else 
	        cout << "Don't intersect";
	} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a
	else {
	    if (slope1 == 0 && slope2 == 0 && f1 && f2) {
		    if (x1 == x4 &&  projectionsIntersect(y1, y2, y3, y4))
        	    cout << "Overlap";
            else if (x1 != x4)
        	    cout << "Paralell";
            else
                cout << "On the same line, but don't intersect";
	    } // Блок для двух прямых вида x = a
        else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {
        	if (f1) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);	
        	}
        	yIntersection = y1;
        	xIntersection = x3;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
            else 
               	cout << "Don't intersect";
        } // Блок для прямых вида y = b и x = a
        else if (slope1 == 0 ^ slope2 == 0) {
        	if (slope1 == 0) {
        		swap(x1, x3);
        		swap(x2, x4);
        		swap(y1, y3);
        		swap(y2, y4);
        		swap(yIntercept1, yIntercept2);
        	}
        	xIntersection = x3;
        	yIntersection = x3 + yIntercept1;
        	if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) 
        		cout << "Intersect at a point ("  << xIntersection << "," << yIntersection << ")";
        	else 
        		cout << "Don't intersect";
        } // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b
    } // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a
	return 0;
}

100

101

102

103

104

105

106

107

108

109

#include <iostream>

#include <math.h>

using namespace std;

bool areCollinear(double x1, double y1, double x2, double y2) {

return x1 / x2 == y1 / y2 ? true : false;// проверка на коллинеарность

}

double getMin(double x1, double x2) {

return x1 < x2 ? x1 : x2;

}

double getMax(double x1, double x2) {

return x1 > x2 ? x1 : x2;

}

// Проверка на пересечение проекций на оси, посредством нахождения взаимного расположения концов проекций

bool projectionsIntersect(double x1, double x2, double x3, double x4) {

return ((getMin(x1, x2) <= getMin(x3, x4) && getMin(x3, x4) <= getMax(x1, x2)) || ((getMin(x3, x4) <= getMin(x1, x2) && getMin(x1, x2) <= getMax(x3,x4))));

}

// Вычисление коэффициента угла наклона уравнения прямой

double getSlope(double x1, double y1, double x2, double y2) {

return (y2 - y1) / (x2 - x1);

}

// Вычисление свободного члена уравнения прямой

double getYIntercept(double x1, double y1, double x2, double y2) {

return (x2 * y1 - x1 * y2) / (x2 - x1);

}

// Нахождение косинуса угла между векторами

double getCos(double x1, double y1, double x2, double y2) {

return (x1 * x2 + y1 * y2) / (sqrt(x1 * x1 + y1 * y1) + sqrt(x2 * x2 + y2 * y2));

}

int main() {

double slope1, slope2; // Коэффициенты углов наклона уравнений прямых, на которых расположены отрезки

bool f1 = false, f2 = false; // Логические флаги для прямых вида x = a

double yIntercept1, yIntercept2; // Свободные члены уравнений прямых, на которых расположены отрезки

double xIntersection, yIntersection; // Координаты точки пересечения, если она существует

double x1, y1, x2, y2, x3, y3, x4, y4; // Заданные координаты концов отрезков

cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3 >> x4 >> y4;

double vx1 = x2 - x1;

double vy1 = y2 - y1; // Вычислим координаты векторов,

double vx2 = x4 - x3; // Задаваемых данными отрезками

double vy2 = y4 - y3;

slope1 = (vx1 != 0 ? getSlope(x1, y1, x2, y2) : 0); // Для прямых вида x = a

slope2 = (vx2 != 0 ? getSlope(x3, y3, x4, y4) : 0); // Присваиваем значение 0 коэффициенту угла наклона

vx1 != 0 ? yIntercept1 = getYIntercept(x1, y1, x2, y2) : f1 = true; // Для прямых вида x = a

vx2 != 0 ? yIntercept2 = getYIntercept(x3, y3, x4, y4) : f2 = true; // Присваиваем флагу значение true

if (!f1 && !f2) {

xIntersection = (yIntercept2 - yIntercept1) / (slope1 - slope2); // Находим решение системы уравнений

yIntersection = slope1 * xIntersection + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0) // Проверяем находится ли точка на обоих отрезках

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else if (yIntercept1 == yIntercept2) {

if (projectionsIntersect(x1, x2, x3, x4))

cout << "Overlap";

else

cout << "On the same line, but don't intersect";

}

else if (yIntercept1 != yIntercept2 && (areCollinear(vx1, vy1, vx2, vy2) || (y1 == y2 && y3 == y4)))

cout << "Paralell";

else

cout << "Don't intersect";

} // Блок нахождения расположения для всех отрезков, кроме тех, где хотя бы один из них расположен на прямой вида x = a

else {

if (slope1 == 0 && slope2 == 0 && f1 && f2) {

if (x1 == x4 && projectionsIntersect(y1, y2, y3, y4))

cout << "Overlap";

else if (x1 != x4)

cout << "Paralell";

else

cout << "On the same line, but don't intersect";

} // Блок для двух прямых вида x = a

else if (f1 ^ f2 && slope1 == 0 && slope2 == 0) {

if (f1) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

yIntersection = y1;

xIntersection = x3;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок для прямых вида y = b и x = a

else if (slope1 == 0 ^ slope2 == 0) {

if (slope1 == 0) {

swap(x1, x3);

swap(x2, x4);

swap(y1, y3);

swap(y2, y4);

swap(yIntercept1, yIntercept2);

}

xIntersection = x3;

yIntersection = x3 + yIntercept1;

if (getCos(x1 - xIntersection, y1 - yIntersection, x2 - xIntersection, y2 - yIntersection) <= 0 && getCos(x3 - xIntersection, y3 -yIntersection, x4 - xIntersection, y4 - yIntersection) <= 0)

cout << "Intersect at a point (" << xIntersection << "," << yIntersection << ")";

else

cout << "Don't intersect";

} // Блок нахождения расположения, когда только одна пряма имеет вид x = a, а вторая y = kx +b

} // Блок нахождения расположения, если хотя бы один отрезок находится на прямой вида x = a

return 0;

}

Код программы

Аналогичная задача на сайте e-olymp:
839. Пересечение отрезков (Засчитанное решение)

Related Images:

Ю2.30. Отрезки на плоскости

30/09/2015 by Грешилов Константин

Задача взята со сборника задач Юркина А. Г.

Условие:

Найти расстояние между двумя произвольно заданными на плоскости отрезками.

Входные данные:

8 чисел, пары координат каждого конца отрезков.

Выходные данные:

Минимальное расстояние между отрезками.

Тесты:

[latex]x_1[/latex]	[latex]y_1[/latex]	[latex]x_2[/latex]	[latex]y_2[/latex]	[latex]x_3[/latex]	[latex]y_3[/latex]	[latex]x_4[/latex]	[latex]y_4[/latex]	Минимальное расстояние
0	0	2	2	1	1	0	3	0
1	2	3	2	2	1	2	0	1
1	1	3	1	1	2.5	3	2.5	1.5
1	-1	3	-1	1	2.5	3	3.5	3.5

Решение:

#include <iostream>
#include <cmath>
#include <algorithm>//библиотека, содержащая функции min и max
using namespace std;
double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double x;
	x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));
	return x;
}
double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double y;
	y=(x-x1)*(y2-y1)/(x2-x1)+y1;
	return y;
}
int main() {
	double x, y, x1, x2, x3, x4, y1, y2, y3, y4, temp;
	cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;
	double mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); //предположим, что минимальное значение, это расстояние от конца одного отрезка до конца другого
	temp=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); //для каждой пары концов разных отрезков высчитываем расстояние между ними
	if (temp<mini)//если оно меньше минимума
	mini=temp;//то меняем минимум
	temp=sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1));//повторяем для каждой пары концов разных отрезков
	if (temp<mini)
	mini=temp;
	temp=sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2));
	if (temp<mini)
	mini=temp;
	x=perpendicularx(x1, y1, x2, y2, x3, y3);//получаем абциссу проекции конца одного отрезка на другой 
	y=perpendiculary(x1, y1, x2, y2, x3, y3, x);//ординату
	if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) //в случае, если равно нулю, абцисса будет равна бесконечности, а это возможно в том случае, если конец отрезка совпадает с его проекцией на другой отрезок
	{
		x=x3; // для корректных вычислений приравниваем абциссы и ординаты точки с её проекцией
		y=y3;
	}
	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) //если проекция лежит на отрезке заданном
	{
		temp=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y));//то проверяем, будет ли расстояние от конца отрезка до её проекции меньше, чем текущий минимум
		if (temp<mini)
		mini=temp;//если да, то меняем значение минимума
	}
	x=perpendicularx(x1, y1, x2, y2, x4, y4); // далее повторяемя для трех других концов отрезков
	y=perpendiculary(x1, y1, x2, y2, x4, y4, x);
	if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0)
	{
		x=x4;
		y=y4;
	}
	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))
	{
		temp=sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y));
		if (temp<mini)
		mini=temp;
	}
	x=perpendicularx(x3, y3, x4, y4, x1, y1);
	y=perpendiculary(x3, y3, x4, y4, x1, y1, x);
	if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)
	{
		x=x1;
		y=y1;
	}
	if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))
	{
		temp=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));
		if (temp<mini)
		mini=temp;
	}
	x=perpendicularx(x3, y3, x4, y4, x2, y2);
	y=perpendiculary(x3, y3, x4, y4, x2, y2, x);
	if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)
	{
		x=x2;
		y=y2;
	}
	if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))
	{
		temp=sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));
		if (temp<mini)
		mini=temp;
	}
	cout<<mini<<endl; // выводим минимальное расстояние и переходим на новую строку
	return 0;
}

#include <iostream>

#include <cmath>

#include <algorithm>//библиотека, содержащая функции min и max

using namespace std;

double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок

{

double x;

x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));

return x;

}

double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок

{

double y;

y=(x-x1)*(y2-y1)/(x2-x1)+y1;

return y;

}

int main() {

double x, y, x1, x2, x3, x4, y1, y2, y3, y4, temp;

cin>>x1>>y1>>x2>>y2>>x3>>y3>>x4>>y4;

double mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1)); //предположим, что минимальное значение, это расстояние от конца одного отрезка до конца другого

temp=sqrt((x3-x2)*(x3-x2)+(y3-y2)*(y3-y2)); //для каждой пары концов разных отрезков высчитываем расстояние между ними

if (temp<mini)//если оно меньше минимума

mini=temp;//то меняем минимум

temp=sqrt((x4-x1)*(x4-x1)+(y4-y1)*(y4-y1));//повторяем для каждой пары концов разных отрезков

if (temp<mini)

mini=temp;

temp=sqrt((x4-x2)*(x4-x2)+(y4-y2)*(y4-y2));

if (temp<mini)

mini=temp;

x=perpendicularx(x1, y1, x2, y2, x3, y3);//получаем абциссу проекции конца одного отрезка на другой

y=perpendiculary(x1, y1, x2, y2, x3, y3, x);//ординату

if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0) //в случае, если равно нулю, абцисса будет равна бесконечности, а это возможно в том случае, если конец отрезка совпадает с его проекцией на другой отрезок

{

x=x3; // для корректных вычислений приравниваем абциссы и ординаты точки с её проекцией

y=y3;

}

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2)) //если проекция лежит на отрезке заданном

{

temp=sqrt((x3-x)*(x3-x)+(y3-y)*(y3-y));//то проверяем, будет ли расстояние от конца отрезка до её проекции меньше, чем текущий минимум

if (temp<mini)

mini=temp;//если да, то меняем значение минимума

}

x=perpendicularx(x1, y1, x2, y2, x4, y4); // далее повторяемя для трех других концов отрезков

y=perpendiculary(x1, y1, x2, y2, x4, y4, x);

if ((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1)==0)

{

x=x4;

y=y4;

}

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

{

temp=sqrt((x4-x)*(x4-x)+(y4-y)*(y4-y));

if (temp<mini)

mini=temp;

}

x=perpendicularx(x3, y3, x4, y4, x1, y1);

y=perpendiculary(x3, y3, x4, y4, x1, y1, x);

if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)

{

x=x1;

y=y1;

}

if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))

{

temp=sqrt((x1-x)*(x1-x)+(y1-y)*(y1-y));

if (temp<mini)

mini=temp;

}

x=perpendicularx(x3, y3, x4, y4, x2, y2);

y=perpendiculary(x3, y3, x4, y4, x2, y2, x);

if ((x4-x3)*(x4-x3)-(y4-y3)*(y4-y3)==0)

{

x=x2;

y=y2;

}

if (x>=min(x3,x4)&&x<=max(x3,x4)&&y>=min(y3,y4)&&y<=max(y3,y4))

{

temp=sqrt((x2-x)*(x2-x)+(y2-y)*(y2-y));

if (temp<mini)

mini=temp;

}

cout<<mini<<endl; // выводим минимальное расстояние и переходим на новую строку

return 0;

}

Описание решения:

При решении задачи использовались переменные типа [latex]double[/latex], так как в условии не поставлено ограничение на координаты концов отрезков, а тип [latex]double[/latex] существенно расширяет диапазон вводимых значений. Решение данной задачи сводится к тому, чтобы найти расстояния между концами разных отрезков и длины перпендикуляров, опущенных с концов одного отрезка на другой. Поэтому, условно разобьем задачу на два пункта:

1.Нахождение расстояния между концами двух отрезков.

2.Нахождение длины перпендикуляров, опущенных с концов одного отрезка на другой.

1.Расстояние между двумя точками [latex]M_1(mx_1,my_1), M_2(mx_2,my_2)[/latex] находится по формуле [latex]\sqrt{(mx_2-mx_1)^2+(my_2-my_1)^2}[/latex]. Сначала, переменной [latex]mini[/latex] присваиваем значение расстояния между первой парой концов отрезков:

mini=sqrt((x3-x1)*(x3-x1)+(y3-y1)*(y3-y1));

20	mini=sqrt((x3-x1)(x3-x1)+(y3-y1)(y3-y1));

Далее, для всех остальных пар концов отрезков находим расстояние между ними, и если оно меньше чем [latex]mini[/latex], то меняем его значение.

После 4 проверок получаем минимальное расстояние между концами двух отрезков.

После этого переходим к пункту 2.

2. Для того, чтобы найти длину перпендикуляра, опущенного с конца одного отрезка на другой, необходимо решить систему, в которой первое уравнение — это уравнение прямой, содержащей концы отрезка, на который опускается перпендикуляр, а второе — уравнение прямой, содержащей этот перпендикуляр.

Продемонстрируем решение для отрезка с координатами [latex](x_1, y_1)[/latex] и [latex](x_2, y_2)[/latex], и точки с координатами [latex](x_3, y_3)[/latex]

Первое уравнение имеет вид [latex](x-x_1)/(x_2-x_1)=(y-y_1)/(y_2-y_1)[/latex], а второе : [latex]-(x_2-x_1)/(y_2-y_1)*(x-x_3)=y-y_3[/latex]. Решив эту систему, получаем, что

x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1))

8	x=(-x1(y2-y1)(y2-y1)+x3(x2-x1)(x2-x1)-y1y2+y1y1)/((x2-x1)(x2-x1)-(y2-y1)(y2-y1))

y=(x-x1)*(y2-y1)/(x2-x1)+y1

14	y=(x-x1)*(y2-y1)/(x2-x1)+y1

Если делитель в [latex]x[/latex] равен нулю, то это означает, что проекция лежит на начале перпендикуляра, то есть они совпадают, и в таком случае присваиваем координатам проекции значения координат точки, с которой опускался перпендикуляр.

Получили абсциссу и ординату проекции точки на отрезок. Необходимо проверить, принадлежит ли эта проекция отрезку, для этого воспользуемся функциями [latex]min[/latex] и [latex]max[/latex], чтобы определить большие из координат отрезка, и операций сравнения:

if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

37	if (x>=min(x1,x2)&&x<=max(x1,x2)&&y>=min(y1,y2)&&y<=max(y1,y2))

Если условия выполняются, то находим длину перпендикуляра по аналогии с расстоянием между концами отрезков, и сравниваем с [latex]mini[/latex]. Если длина меньше, то меняем значение минимума.

Так как все шаги нахождения повторяются 4 раза, то вынесем их в отдельные функции, которые высчитывают значения для каждой координаты проекции:

double perpendicularx(double x1,double y1, double x2, double y2, double x3, double y3) //функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double x;
	x=(-x1*(y2-y1)*(y2-y1)+x3*(x2-x1)*(x2-x1)-y1*y2+y1*y1)/((x2-x1)*(x2-x1)-(y2-y1)*(y2-y1));
	return x;
}
double perpendiculary(double x1,double y1, double x2, double y2, double x3, double y3, double x)//функция, которая высчитывает значение абциссы проекции точки на прямую, содержащую отрезок
{
	double y;
	y=(x-x1)*(y2-y1)/(x2-x1)+y1;
	return y;
}