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

Задача

Уезжая из дома, поэт оставлял коту, прикованному к дубу цепью длиной $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]

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

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

Для каждой рыбы мы будем делать такой процесс.
Для начала проверим расстояния от начала координат до каждого из концов рыбы. Если хотя бы одно из них меньше либо равно длине цепи, то кот сможет съесть эту рыбу и ничего больше проверять не надо. Если же эти расстояния больше длины цепи поступим так. Найдем уравнение прямой проходящей через две точки (координаты начала и конца рыбы). Оно имеет вид: $$\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
Код решения

Ю2.15

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

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

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

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

Координаты концов двух отрезков [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

 

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

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

  1. areCollinear — функция, принимающая координаты векторов, задаваемых отрезками, и возвращающая логическое значение true, если они коллинеарны, и false в противном случае.
    ( Основная формула:  [latex]\frac{x_1}{x_2}[/latex] [latex]=[/latex] [latex]\frac{y_1}{y_2}[/latex] )
  2. getMin — возвращает минимум двух чисел.
  3. getMax —  возвращает максимум двух чисел.
  4. projectionsIntersect — функция, принимающая абсциссы или ординаты двух векторов и возвращающая логическое значение true, если проекции отрезков на соответствующую ось пересекаются, и false в противном случае.
  5. getSlope — функция, принимающая координаты отрезка и возвращающая угол наклона прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{y_2 — y_1}{x_2 — x_1}[/latex] )
  6. getYIntercept — функция, принимающая координаты отрезка и возвращающая свободный член уравнения прямой, на которой он расположен.
    ( Основная формула:  [latex]\frac{x_2y_1 — x_1y_2}{x_2 — x_1}[/latex] )
  7. 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 тогда, когда это возможно, так как они будут задействованы в дальнейшем.

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

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

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

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

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

А59и

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

А59и

 

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

[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 Точка не входит в заштрихованную область.

Сам код:

Ссылка на код

 

 

Ю2.5

Четырёхугольник 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) Не выпуклый

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

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

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

Ход решения:

Задаем уравнение прямой ([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.Сравниваем значения вершин. Если их знаки разные — четырёхугольник не выпуклый.

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

А53

Задача: Даны действительные числа [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) принадлежат
разным полуплоскостям

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

По условию задачи нужно выяснить, верно ли, что точки [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: