e-olymp 209. Защита от копирования

29/05/2018 by Александра Рябова

Условие

Давным-давно, в далекой-далекой галактике, когда еще не вышел мультфильм про смешариков, никто не знал про Гарри Поттера и про Властелина Колец, на далекой-далекой планете жили-были полчища смешариков. Их технологии были настолько совершенны, что они создали машину времени и перенеслись на ней в будущее, на планету «Земля», где одному из них совершенно случайно попалась первая серия «Смешариков». Исследователей эта серия так потрясла, что они предприняли чрезвычайно опасный рейд, в ходе которого им удалось добыть полное собрание серий. Эти серии они увезли на родину, где они стали безумно популярными. К сожалению, мультфильмы были с системой защиты от копирования, а смешарики по своей законопослушной сущности не приспособлены к хакерской деятельности. Поэтому им пришлось обмениваться привезенными с Земли дисками.

Местная поп-звезда Билаш обиделся на такую популярность, к которой он не имел никакого отношения, и решил вернуть все в старое русло. Для этого Билаш хочет рассорить смешариков, чтобы они разделились на два не общающихся между собой лагеря. Для того, чтобы поссорить пару смешариков, Билашу требуется израсходовать $1$ у.е. усилий. Но, так как Билаш жутко ленив, он хочет приложить минимум усилий для достижения своей цели. Помогите ему.

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

На первой строке два числа $N$ $(N \le 100)$ и $M$ — количество смешариков и количество пар смешариков, которые обмениваются мультфильмами. На последующих $M$ строках перечисляются пары чисел $U$ и $V$, означающих, что смешарик $U$ и смешарик $V$ знакомы друг с другом и обмениваются мультфильмами.

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

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

Тесты

Ввод	Вывод
$5$ $5$ $1$ $2$ $3$ $2$ $2$ $4$ $3$ $5$ $2$ $5$	$1$
$5$ $5$ $1$ $3$ $3$ $5$ $5$ $2$ $2$ $4$ $4$ $1$	$2$
$2$ $1$ $2$ $1$	$1$

Код

#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 500;
int g[MAXN][MAXN];
int best_cost = 1000000000;
 
void mincut(int n) {
    vector< int> v[MAXN];
    for (int i = 0; i < n; ++i) v[i].assign (1, i);
    int w[MAXN];
    bool exist [MAXN], in_a [MAXN];
    for (auto &e :exist) e = true;
    for (int ph = 0; ph < n-1; ++ph) {
        for (auto &e: in_a) e = false;
        for (auto &e: w) e = 0;
        for (int it = 0, prev; it< n-ph; ++it) {
            int sel = -1;
            for (int i = 0; i < n; ++i)
                if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel])) sel = i;
            if (it == n-ph-1) {
                if (w[sel] < best_cost)
                    best_cost = w[sel];
                v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());
                for (int i=0; i<n; ++i)
                    g[prev][i] = g[i][prev] += g[sel][i];
                exist[sel] = false;
            }
            else {
                in_a[sel] = true;
                for (int i = 0; i < n; ++i) w[i] += g[sel][i];
                prev = sel;
            }
        }
    }
}
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++){
        int a,b;
        cin >> a >> b;
        a--;
        b--;
        g[a][b] = 1;
        g[b][a] = 1;
    }
    mincut (n);
    cout << best_cost;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

const int MAXN = 500;

int g[MAXN][MAXN];

int best_cost = 1000000000;

void mincut(int n) {

vector< int> v[MAXN];

for (int i = 0; i < n; ++i) v[i].assign (1, i);

int w[MAXN];

bool exist [MAXN], in_a [MAXN];

for (auto &e :exist) e = true;

for (int ph = 0; ph < n-1; ++ph) {

for (auto &e: in_a) e = false;

for (auto &e: w) e = 0;

for (int it = 0, prev; it< n-ph; ++it) {

int sel = -1;

for (int i = 0; i < n; ++i)

if (exist[i] && !in_a[i] && (sel == -1 || w[i] > w[sel])) sel = i;

if (it == n-ph-1) {

if (w[sel] < best_cost)

best_cost = w[sel];

v[prev].insert (v[prev].end(), v[sel].begin(), v[sel].end());

for (int i=0; i<n; ++i)

g[prev][i] = g[i][prev] += g[sel][i];

exist[sel] = false;

}

else {

in_a[sel] = true;

for (int i = 0; i < n; ++i) w[i] += g[sel][i];

prev = sel;

}

int main() {

int n, m;

cin >> n >> m;

for (int i = 0; i < m; i++){

int a,b;

cin >> a >> b;

a--;

b--;

g[a][b] = 1;

g[b][a] = 1;

}

mincut (n);

cout << best_cost;

return 0;

}

Решение

Зададим связи между смешариками в виде графов, где сами смешарики являются вершинами, смежными в том случае, если они дружат. Тогда задача сводится к нахождению минимального количества ребер, которые необходимо удалить в графе, чтобы разбить его на две не связанные между собою компоненты. Такую постановку задачи полностью решает алгоритм Штор-Вагнера в несколько упрощенном виде, так как нам не нужно знать, какие именно ребра графа надо разорвать, а достаточно подсчитать их количество.

Ссылки

Условие на e-olymp.com
Код на ideone.com

Related Images:

e-olymp 7457. Max-Min в двійковій системі счислення

20/12/2017 by Александра Рябова

Умова

Вивчаючи двійкову систему числення, Василько вирішив попрактикуватися і придумав таку вправу. Він із бітів числа створював найбільше і найменше число, переставляючи біти, після чого знаходив їх різницю. Проте хлопець не знає, чи правильно виконує вправу. Допоможіть йому. Напишіть програму, яка за даним числом [latex]N[/latex] знаходить різницю між найбільшим і найменшим числом, які утворюються із бітів заданого числа. У найбільшого числа найбільший біт співпадає з найбільшим бітом заданого числа.

Пояснення

[latex]N = 13_{10}[/latex], в двійковій системі числення — [latex]1101_2[/latex], найбільше число [latex]1110_2[/latex] = [latex]14_{10}[/latex], найменше число [latex]0111_2[/latex] = [latex]7_{10}[/latex]. [latex]14-7=7[/latex].

Вхідні дані

В єдиному рядку записане число N ([latex]N<2^{31}[/latex]).

Вихідні дані

Єдине число — відповідь до вправи Василька.

Тести

Вхідні дані	Вихідні дані
$2$	$1$
$15$	$0$
$86$	$105$
$1000$	$945$
$40$	$45$

Код програми

#include <iostream>
#include <iomanip>
#include <cmath>

long long max_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n0+n1-1; i>=n0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

long long min_number(long long n1, long long n0)
{
    long long  number;
    for (int i=n1-1; i>=0; i--)
    {
        number+=pow(2, i);  
    }
    return(number);
}

int main() 
{
    long long n;
    cin >> n;
    long long n1=0;
    long long n0=0;
    while (n>0)
    {
        if (n%2==1) n1++;
        else n0++;
        n/=2;
    }
    
    cout << max_number (n1, n0) - min_number (n1, n0);
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

long long max_number(long long n1, long long n0)

{

long long number;

for (int i=n0+n1-1; i>=n0; i--)

{

number+=pow(2, i);

}

return(number);

}

long long min_number(long long n1, long long n0)

{

long long number;

for (int i=n1-1; i>=0; i--)

{

number+=pow(2, i);

}

return(number);

}

int main()

{

long long n;

cin >> n;

long long n1=0;

long long n0=0;

while (n>0)

{

if (n%2==1) n1++;

else n0++;

n/=2;

}

cout << max_number (n1, n0) - min_number (n1, n0);

return 0;

}

Рішення

Процес вирішення даної задачі поділяється на 4 кроки:

За допомогою циклу рахуємо кількість одиниць та нулів у двійковому вигляді поданого числа [latex]n[/latex].
Створимо функцію [latex]max\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найбільше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Очевидно, що отримати найбільше число в двійковому вигляді можна, якщо записати спочатку всі одиниці, а потім — усі нулі.
Створимо функцію [latex]min\_number[/latex], яка за поданою кількістю нулів та одиниць буде повертати найменше число, яке в двійковій формі складатиметься з цієї кількості одиниць та нулів. Зрозуміло, що найменше число буде виглядати навпаки — спочатку будуть стояти всі нулі, а потім — усі одиниці.
Виведемо на екран різницю підрахованих функціями [latex]max\_number[/latex] та [latex]min\_number[/latex] значень.

Посилання

Код програми на ideone
Умова на сайті E-Olymp

Related Images:

e-olymp 7337. Скидки

06/11/2017 by Мороз Дима

Задача

В супермаркете электроники, если верить телерекламе, существует система скидок: из двух купленных товаров полностью оплачивается только стоимость товара, который дороже, а другой отдается бесплатно. Какой суммы достаточно, что бы оплатить покупку трёх товаров, если известна цена каждого?
Входные данные: три натуральных числа $a, b, c$ — цены трёх товаров $\left(1 ≤ a, b, c ≤ 10000 \right).$
Выходные данные: стоимость покупки.

Тесты

Входные данные	Выходные данные
213 6554 234	6767
320 3670 5555	5875
15 47 13	60
215 30 73	245
370 53 823	876

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

#include <iostream>
using namespace std;

int main(){
    int a, b, c;
    cin >> a >> b >> c;
    cout << max(max(a, b), c) + min(min(a, b), c);
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int a, b, c;

cin >> a >> b >> c;

cout << max(max(a, b), c) + min(min(a, b), c);

return 0;

}

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

Для нахождения самого дорогого и самого дешёвого товаров мы используем встроенные функции $\min \left(\right)$ и $\max \left(\right)$. Находим минимальное число среди чисел $a$, $b$ и $c$: $\min \left(\min \left(a, b \right), c \right)$ (пример: $\min \left(\min \left(1, 2 \right), 3 \right) = 1$). Далее проводим такую же операцию с нахождением максимального числа среди $a$, $b$ и $c$: $\max \left(\max \left(a, b \right), c \right)$ (пример: $\max \left(\max \left(1, 2 \right), 3 \right) = 3$). Затем суммируем полученные минимальное и максимальное числа и получаем ответ.

Ссылки

Условие задачи на e-olymp.com
Код задачи на ideone.com

Related Images:

Mif3

09/10/2015 by Кирилл Демиденко

Задача

Даны действительные числа [latex] x [/latex], [latex] y [/latex], [latex] z [/latex]. Получить [latex]min\left ( x,y,z \right )[/latex] .

Тесты

Входные данные:	4 3 2	0 2 1	0 -1 4	2 3 4
Выходные данные:	2	0	-1	2

#include <iostream>
using namespace std;
int main()
{
    double x, y, z; 
    cin >> x >> y >> z;
    double min = x; // x- минимальное 
    if (y < min) { // сравниваем y с x
        min = y; // и если y меньше, то выводим y
    }
    if (z < min) { // сравниваем z с x
        min = z; // если z меньше, то выводим z
    }
    cout << min << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double x, y, z;

cin >> x >> y >> z;

double min = x; // x- минимальное

if (y < min) { // сравниваем y с x

min = y; // и если y меньше, то выводим y

}

if (z < min) { // сравниваем z с x

min = z; // если z меньше, то выводим z

}

cout << min << endl;

return 0;

}

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

Предположим, что [latex] x [/latex] минимальное из трёх чисел, и путем сравнения с [latex]y[/latex] выясняем, какое из этих двух чисел минимальное. Если [latex]x[/latex] остается минимальным, то сравниваем его с [latex]z[/latex], а если [latex]y[/latex] окажется меньше, то его сравниваем с [latex]z[/latex] и после выводим минимальное из трех чисел на экран.

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;
}