e-olymp 49. Кот учёный

09/05/2018 by Костя Григорян

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $l$, $n$ рыбин. Зная координаты головы и хвоста каждой из них, подсчитайте, на какие сутки у кота визникнет чувство голода, если оно возникает тогда, когда за сутки он съест меньше, чем $k$ рыбин. Рыбину он может съесть, если сможет дотянуться хотя бы к одной её точке. Координаты дуба $(0, 0)$.

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

В первой строке находятся числа $l$, $n$, $k$. Далее идет $n$ строк: координаты головы $(x_{1i}, y_{1i})$ и хвоста $(x_{2i}, y_{2i})$ каждой рыбины. Все входные данные — целые числа, не превышающие по модулю $100$.

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

Вывести день, на который у кота появится чувство голода.

Тесты

Входные данные	Выходные данные
[latex]4\, 4\, 2[/latex]	[latex]2[/latex]
[latex]1\, 1\, -1\, 3[/latex]
[latex]2\, 2\, 4\, 2[/latex]
[latex]-3\, -4\, -3\, 4[/latex]
[latex]1\, -5\, 4\, -4[/latex]
[latex]3\, 2\, 1[/latex]	[latex]3[/latex]
[latex]1\, 2\, 3\, 4[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]3\, 5\, 4[/latex]	[latex]1[/latex]
[latex]2\, 4\, 5\, 7[/latex]
[latex]1\, -1\, -1\, 1[/latex]
[latex]8\, 10\, 2\, 7[/latex]
[latex]12\, 3\, 4\, 2[/latex]
[latex]100\, 100\, -100\, -100[/latex]

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

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int l, n, k, count=0;
    cin >> l >> n >> k;
    for(int i=0; i<n; i++)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)
            count++;
        else
        {
            int a, b, c;
            int deltaX=x2-x1;
            int deltaY=y2-y1;
            a=deltaY;
            b=-deltaX;
            c=y1*deltaX-x1*deltaY;
            if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))
                count++;
        }
    }
    cout << count/k+1 << endl; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int l, n, k, count=0;

cin >> l >> n >> k;

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

{

int x1, y1, x2, y2;

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

if(x1*x1+y1*y1<=l*l||x2*x2+y2*y2<=l*l)

count++;

else

{

int a, b, c;

int deltaX=x2-x1;

int deltaY=y2-y1;

a=deltaY;

b=-deltaX;

c=y1*deltaX-x1*deltaY;

if(c*c<=l*l*(a*a+b*b)&&(-c*b<=(b*b+a*a)*max(y2, y1)&&-c*b>=(b*b+a*a)*min(y2, y1)))

count++;

}

cout << count/k+1 << endl;

return 0;

}

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\frac{x-x_1}{x_2-x_1}=\frac{y-y_1}{y_2-y_1}$$ Приведем его к виду $ax+by+c=0$. Получим, что $a=y_2-y_1$, $b=-(x_2-x_1)$, $c=y_1(x_2-x_1)-x_1(y_2-y_1)$. Теперь проверим длину перпендикуляра к этой прямой от начала координат (т. к. если длина перпендикуляра больше длины цепи, кот точно не дотянется до рыбы). Расстояние $d$ от точки $(0,0)$ до прямой $ax+by+c=0$ посчитаем по формуле: $$d=\frac{a\cdot 0+b\cdot 0+c}{\sqrt{a^2+b^2}}$$ Избавляясь от корня и деления, получим условие: $$c^2\leq l^2(a^2+b^2)$$ (где $l$ — длина цепи). Если это условие выполняется, остается проверить, что точка пересечения перпендикуляра и прямой лежит между началом и концом рыбы (нам достаточно проверить по одной из координат, например по второй). Прямая, перпендикулярная исходной и проходящая через точку $(0,0)$, будет иметь вид: $$\frac{x}{a}=\frac{y}{b}$$ (т. к. $(a,b)$ — нормальный вектор к прямой, проходящей через начало и конец рыбы). Получаем систему из двух уравнений и двух неизвестных. Решая эту систему, получаем, что вторая координата точки пересечения равна: $$y=\frac{-cb}{a^2+b^2}$$ Теперь проверяем, лежит ли эта координата, между вторыми координатами начала и конца рыбы. Если да, то кот сможет съесть эту рыбу, иначе — нет.
Ответом на задачу будет $\left \lfloor\frac{count}{k}\right \rfloor+1$, где $count$ — количество рыб, до которых смог дотянуться кот, $k$ — минимальное количество рыб, которое кот должен съесть в сутки.

Ссылки

Условие задачи на e-olymp
Код решения

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:

А59и

12/11/2014 by Носуленко Марк

Даны действительные числа [latex]x, y[/latex]. Определить, принадлежит ли точка с координатами [latex]x, y[/latex] заштрихованной части плоскости.

Вычислил уравнения прямых по формуле :

[latex]\frac{x-x_{a}}{x_{b}-x_{a}}=\frac{y-y_{a}}{y_{a}-y_{b}}[/latex]

Получил уравнения :

[latex]y=2x+3[/latex], [latex]y=-x[/latex], [latex]y=\frac{x-1}{3}[/latex]

Плоскость разделил на верхнюю и нижнюю части осью ox([latex]y\geq 0[/latex], [latex]y\leq 0[/latex]), при помощи первых двух уравнений выделил заштрихованную область в верхней части, при помощи первого и третьего соответственно в нижней(изменив знак «=» на «≥» или «≤»(в зависимости от того где должна лежать точка для выполнения условия) ).

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Результат:
-2	-1	Точка входит в заштрихованную область.
-2	-1.001	Точка не входит в заштрихованную область.
-2	-0.999	Точка не входит в заштрихованную область.
-1	1	Точка входит в заштрихованную область.
-1.001	1	Точка не входит в заштрихованную область.
-1	1.001	Точка не входит в заштрихованную область.
-1	0.999	Точка входит в заштрихованную область.
1	0	Точка входит в заштрихованную область.
1	-0.001	Точка не входит в заштрихованную область.

Сам код:

using namespace std;

int main() {
	double x, y;
	cin >> x >> y;
	if(y>=0 && y<=-x && x>=(y-3)/2 || y<=0 && x>=(y-3)/2 && y>=(x-1)/3)
		cout << "Точка входит в заштрихованную область.";
	else
		cout << "Точка не входит в заштрихованную область.";
	return 0;
}

using namespace std;

int main() {

double x, y;

cin >> x >> y;

if(y>=0 && y<=-x && x>=(y-3)/2 || y<=0 && x>=(y-3)/2 && y>=(x-1)/3)

cout << "Точка входит в заштрихованную область.";

else

cout << "Точка не входит в заштрихованную область.";

return 0;

}

Ссылка на код

Related Images:

Ю2.5

26/10/2014 by Стеблинський Ігор Віталійович

Четырёхугольник ABCD задан координатами своих вершин на плоскости: A([latex]x_{a}[/latex],[latex]y_{a}[/latex]), B([latex]x_{b}[/latex],[latex]y_{b}[/latex]), C([latex]x_{c}[/latex],[latex]y_{c}[/latex]), D([latex]x_{d}[/latex],[latex]y_{d}[/latex]). Проверить, является ли он выпуклым.

Тесты:

Точки	Координаты (x,y)	Вердикт
A,B,C,D	(1,1),(3,3),(5,2),(2,0)	Выпуклый
A,B,C,D	(-2,1),(2,2),(3,-1),(3,-1)	Выпуклый
A,B,C,D	(1,0),(1,3),(2,1),(5,0)	Не выпуклый
A,B,C,D	(-1,3),(0,0),(4,2),(-1,-3)	Не выпуклый

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

#include <iostream>
#include <math.h>
using namespace std;
int f (int x, int x0, int x1, int y, int y0, int y1)
{
	return  (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);
} 
int main() {
	double xa, ya, xb, yb, xc, yc, xd, yd;
	cin >> xa >> ya >> xb >> yb >> xc >> yc >> xd >> yd;
	int l,m;
	l = f(xc,xb,xa,yc,yb,ya);
	m = f(xd,xb,xa,yd,yb,ya);
	if (l * m < 0) {
		printf("не выпуклый");
		return 0;
	}
	int q,w;
	q = f(xa,xc,xb,ya,yc,yb);
	w = f(xd,xc,xb,yd,yc,yb);
	if (q * w < 0) {
		printf("не выпуклый");
		return 0;
	}
	int p,r;
	p = f(xa,xd,xc,ya,yd,yc);
	r = f(xb,xd,xc,yb,yd,yc);
	if (p * r < 0) {
		printf("не выпуклый");
		return 0;
	}
	int j,k;
	j = f(xb,xa,xd,yb,ya,yd);
	k = f(xc,xa,xd,yc,ya,yd);
	if (j * k < 0) {
		printf("не выпуклый");
		return 0;
	}

	printf ("Выпуклый");
	return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int f (int x, int x0, int x1, int y, int y0, int y1)

{

return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);

}

int main() {

double xa, ya, xb, yb, xc, yc, xd, yd;

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

int l,m;

l = f(xc,xb,xa,yc,yb,ya);

m = f(xd,xb,xa,yd,yb,ya);

if (l * m < 0) {

printf("не выпуклый");

return 0;

}

int q,w;

q = f(xa,xc,xb,ya,yc,yb);

w = f(xd,xc,xb,yd,yc,yb);

if (q * w < 0) {

printf("не выпуклый");

return 0;

}

int p,r;

p = f(xa,xd,xc,ya,yd,yc);

r = f(xb,xd,xc,yb,yd,yc);

if (p * r < 0) {

printf("не выпуклый");

return 0;

}

int j,k;

j = f(xb,xa,xd,yb,ya,yd);

k = f(xc,xa,xd,yc,ya,yd);

if (j * k < 0) {

printf("не выпуклый");

return 0;

}

printf ("Выпуклый");

return 0;

}

Ссылка на код http://ideone.com/dsWBJc

import java.util.*;
import java.lang.*;
import java.io.*;
 
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	static double f (double x, double x0, double x1, double y, double y0, double y1){
		return  (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);
	}
	public static void main (String[] args) throws java.lang.Exception
	{
		double xa, ya, xb, yb, xc, yc, xd, yd;
		Scanner in = new Scanner(System.in);
		xa = in.nextDouble();
		ya = in.nextDouble();
		xb = in.nextDouble();
		yb = in.nextDouble();
		xc = in.nextDouble();
		yc = in.nextDouble();
		xd = in.nextDouble();
		yd = in.nextDouble();
		double l,m;
		l = f(xc,xb,xa,yc,yb,ya);
		m = f(xd,xb,xa,yd,yb,ya);
		if (l * m < 0) {
			System.out.printf("не выпуклый");
			return;
		}
		double q,w;
		q = f(xa,xc,xb,ya,yc,yb);
		w = f(xd,xc,xb,yd,yc,yb);
		if (q * w < 0) {
			System.out.printf("не выпуклый");
			return;
		}
		double p,r;
		p = f(xa,xd,xc,ya,yd,yc);
		r = f(xb,xd,xc,yb,yd,yc);
		if (p * r < 0) {
			System.out.printf("не выпуклый");
			return;
		}
		double j,k;
		j = f(xb,xa,xd,yb,ya,yd);
		k = f(xc,xa,xd,yc,ya,yd);
		if (j * k < 0) {
			System.out.printf("не выпуклый");
			return;
		}
		System.out.printf(" Выпуклый ");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */

class Ideone

{

static double f (double x, double x0, double x1, double y, double y0, double y1){

return (x - x0) * (y1 - y0) - (y - y0) * (x1 - x0);

}

public static void main (String[] args) throws java.lang.Exception

{

double xa, ya, xb, yb, xc, yc, xd, yd;

Scanner in = new Scanner(System.in);

xa = in.nextDouble();

ya = in.nextDouble();

xb = in.nextDouble();

yb = in.nextDouble();

xc = in.nextDouble();

yc = in.nextDouble();

xd = in.nextDouble();

yd = in.nextDouble();

double l,m;

l = f(xc,xb,xa,yc,yb,ya);

m = f(xd,xb,xa,yd,yb,ya);

if (l * m < 0) {

System.out.printf("не выпуклый");

return;

}

double q,w;

q = f(xa,xc,xb,ya,yc,yb);

w = f(xd,xc,xb,yd,yc,yb);

if (q * w < 0) {

System.out.printf("не выпуклый");

return;

}

double p,r;

p = f(xa,xd,xc,ya,yd,yc);

r = f(xb,xd,xc,yb,yd,yc);

if (p * r < 0) {

System.out.printf("не выпуклый");

return;

}

double j,k;

j = f(xb,xa,xd,yb,ya,yd);

k = f(xc,xa,xd,yc,ya,yd);

if (j * k < 0) {

System.out.printf("не выпуклый");

return;

}

System.out.printf(" Выпуклый ");

}

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

Ход решения:

Задаем уравнение прямой ([latex]\frac{x-x_{0}}{x_{1}-x_{0}}-\frac{y-y_{0}}{y_{1}-y_{0}}[/latex]). Преобразовываем его к виду без деления (чтобы не было проблем с делением на нуль) [latex](x-x_{0})*(y_{1}-y_{0})-(y-y_{0})*(x_{1}-x_{0})[/latex].

Для каждой стороны (AB,BC,CD,AD):

1. Строим уравнение прямой через эти две вершины.

2. Подставляем в формулу координаты остальных вершин.

3.Сравниваем значения вершин. Если их знаки разные — четырёхугольник не выпуклый.

Если для всех сторон данные условия выполнены — четырёхугольник является выпуклым.

Related Images:

А53

22/09/2014 by Зелінський Вячеслав Олександрович

Задача: Даны действительные числа [latex]a,b,c,d,e,f,g,h.[/latex] Известно, что точки [latex](e,f)[/latex] и [latex](g,h)[/latex] различны. Известно также, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] не лежат на прямой [latex]l[/latex], проходящей через точки [latex](e,f)[/latex] и [latex](g,h)[/latex]. Прямая [latex]l[/latex] разбивает координатную плоскость на две полуплоскости. Выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости.

a	b	c	d	e	f	g	h	Комментарий:
1	1	1	1	1	1	1	1	(a,b) и (c,d) принадлежит разным полуплоскостям
2	3	7	5	6	3	5	2	(a,b) и (c,d) принадлежат одной полуплоскости
3	1545	3455	4	42	656,1	3445	1,56	(a,b) и (c,d) принадлежат разным полуплоскостям

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

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

int main() {
      double a, b, c, d, e, f, g, h; //Описание переменных для хранения входных данных. a, b, c, d, e, f, g, h - координаты точек плоскости.
      double f1, f2; //Описание формул, для нахождения координат точек.
      scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f, &g, &h);      //Чтение из стандартного потока. 
      // f=(x-e)(h-f)-(y-f)(g-e) - уравнение прямой.
      f1=(a-e)*(h-f)-(b-f)*(g-e); //Подставляем в f(x,y) точку (a,b)
      f2=(c-e)*(h-f)-(d-f)*(g-e); //Подставляем в f(x,y) точку (c,d)
      if (f1>0 && f2>0 || f1<0 && f2<0)
          printf("Yes");
      else
          printf("No");
      return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main() {

double a, b, c, d, e, f, g, h; //Описание переменных для хранения входных данных. a, b, c, d, e, f, g, h - координаты точек плоскости.

double f1, f2; //Описание формул, для нахождения координат точек.

scanf("%lf %lf %lf %lf %lf %lf %lf %lf", &a, &b, &c, &d, &e, &f, &g, &h); //Чтение из стандартного потока.

// f=(x-e)(h-f)-(y-f)(g-e) - уравнение прямой.

f1=(a-e)*(h-f)-(b-f)*(g-e); //Подставляем в f(x,y) точку (a,b)

f2=(c-e)*(h-f)-(d-f)*(g-e); //Подставляем в f(x,y) точку (c,d)

if (f1>0 && f2>0 || f1<0 && f2<0)

printf("Yes");

else

printf("No");

return 0;

}

По условию задачи нужно выяснить, верно ли, что точки [latex](a,b)[/latex] и [latex](c,d)[/latex] принадлежат одной и той же полуплоскости. Вводим переменные с типом данных «float», так как координаты входят в множество действительных чисел. Определяем взаимное расположение точек с помощью уравнения прямой: [latex]f=(x-e)(h-f)-(y-f)(g-e)[/latex] .

Если точки лежат в одной полуплоскости, то [latex](a-e)*(h-f)-(b-f)*(g-e)[/latex] и
[latex](c-e)*(h-f)-(d-f)*(g-e)[/latex] – должны быть числами одного знака, если же их знаки противоположны, то точки лежат в разных полуплоскостях.

Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone
{
	public static void main (String[] args) 
	{
	 double a, b, c, d, e, f, g, h, f1, f2;
	 Scanner in = new Scanner(System.in);
	 a = in.nextDouble();
	 b = in.nextDouble();
	 c = in.nextDouble();
	 d = in.nextDouble();
	 e = in.nextDouble();
	 f = in.nextDouble();
	 g = in.nextDouble();
	 h = in.nextDouble();
	 f1=(a-e)*(h-f)-(b-f)*(g-e); 
     f2=(c-e)*(h-f)-(d-f)*(g-e); 
     if (f1>0 && f2>0 || f1<0 && f2<0)
         System.out.println("Yes");
     else
         System.out.println("No");
    }
}