В данной статье рассмотрим способы определить расстояние от точки до точки теоретически и на примере конкретных задач. И для начала введем некоторые определения.
Yandex.RTB R-A-339285-1 Определение 1
Расстояние между точками – это длина отрезка, их соединяющего, в имеющемся масштабе. Задать масштаб необходимо, чтобы иметь для измерения единицу длины. Потому в основном задача нахождения расстояния между точками решается при использовании их координат на координатной прямой, в координатной плоскости или трехмерном пространстве.
Исходные данные: координатная прямая O x и лежащая на ней произвольная точка А. Любой точке прямой присуще одно действительное число: пусть для точки А это будет некое число х A , оно же – координата точки А.
В целом можно говорить о том, что оценка длины некого отрезка происходит в сравнении с отрезком, принятым за единицу длины в заданном масштабе.
Если точке А соответствует целое действительное число, отложив последовательно от точки О до точки по прямой О А отрезки – единицы длины, мы можем определить длину отрезка O A по итоговому количеству отложенных единичных отрезков.
К примеру, точке А соответствует число 3 – чтобы попасть в нее из точки О, необходимо будет отложить три единичных отрезка. Если точка А имеет координату - 4 – единичные отрезки откладываются аналогичным образом, но в другом, отрицательном направлении. Таким образом в первом случае, расстояние О А равно 3 ; во втором случае О А = 4 .
Если точка A имеет в качестве координаты рациональное число, то от начала отсчета (точка О) мы откладываем целое число единичных отрезков, а затем его необходимую часть. Но геометрически не всегда возможно произвести измерение. К примеру, затруднительным представляется отложить на координатной прямой дробь 4 111 .
Вышеуказанным способом отложить на прямой иррациональное число и вовсе невозможно. К примеру, когда координата точки А равна 11 . В таком случае возможно обратиться к абстракции: если заданная координата точки А больше нуля, то O A = x A (число принимается за расстояние); если координата меньше нуля, то O A = - x A . В общем, эти утверждения справедливы для любого действительного числа x A .
Резюмируя: расстояние от начала отсчета до точки, которой соответствует действительное число на координатной прямой, равно:
- 0, если точка совпадает с началом координат;
- x A , если x A > 0 ;
- - x A , если x A < 0 .
При этом очевидно, что сама длина отрезка не может быть отрицательной, поэтому, используя знак модуля, запишем расстояние от точки O до точки A с координатой x A : O A = x A
Верным будет утверждение: расстояние от одной точки до другой будет равно модулю разности координат. Т.е. для точек A и B , лежащих на одной координатной прямой при любом их расположении и имеющих соответственно координаты x A и x B: A B = x B - x A .
Исходные данные: точки A и B , лежащие на плоскости в прямоугольной системе координат O x y с заданными координатами: A (x A , y A) и B (x B , y B) .
Проведем через точки А и B перпендикуляры к осям координат O x и O y и получим в результате точки проекции: A x , A y , B x , B y . Исходя из расположения точек А и B далее возможны следующие варианты:
Если точки А и В совпадают, то расстояние между ними равно нулю;
Если точки А и В лежат на прямой, перпендикулярной оси O x (оси абсцисс), то точки и совпадают, а | А В | = | А y B y | . Поскольку, расстояние между точками равно модулю разности их координат, то A y B y = y B - y A , а, следовательно A B = A y B y = y B - y A .
Если точки A и B лежат на прямой, перпендикулярной оси O y (оси ординат) – по аналогии с предыдущим пунктом: A B = A x B x = x B - x A
Если точки A и B не лежат на прямой, перпендикулярной одной из координатных осей, найдем расстояние между ними, выведя формулу расчета:
Мы видим, что треугольник А В С является прямоугольным по построению. При этом A C = A x B x и B C = A y B y . Используя теорему Пифагора, составим равенство: A B 2 = A C 2 + B C 2 ⇔ A B 2 = A x B x 2 + A y B y 2 , а затем преобразуем его: A B = A x B x 2 + A y B y 2 = x B - x A 2 + y B - y A 2 = (x B - x A) 2 + (y B - y A) 2
Сформируем вывод из полученного результата: расстояние от точки А до точки В на плоскости определяется расчётом по формуле с использованием координат этих точек
A B = (x B - x A) 2 + (y B - y A) 2
Полученная формула также подтверждает ранее сформированные утверждения для случаев совпадения точек или ситуаций, когда точки лежат на прямых, перпендикулярных осям. Так, для случая совпадения точек A и B будет верно равенство: A B = (x B - x A) 2 + (y B - y A) 2 = 0 2 + 0 2 = 0
Для ситуации, когда точки A и B лежат на прямой, перпендикулярной оси абсцисс:
A B = (x B - x A) 2 + (y B - y A) 2 = 0 2 + (y B - y A) 2 = y B - y A
Для случая, когда точки A и B лежат на прямой, перпендикулярной оси ординат:
A B = (x B - x A) 2 + (y B - y A) 2 = (x B - x A) 2 + 0 2 = x B - x A
Исходные данные: прямоугольная система координат O x y z с лежащими на ней произвольными точками с заданными координатами A (x A , y A , z A) и B (x B , y B , z B) . Необходимо определить расстояние между этими точками.
Рассмотрим общий случай, когда точки A и B не лежат в плоскости, параллельной одной из координатных плоскостей. Проведем через точки A и B плоскости, перпендикулярные координатным осям, и получим соответствующие точки проекций: A x , A y , A z , B x , B y , B z
Расстояние между точками A и B являет собой диагональ полученного в результате построения параллелепипеда. Согласно построению измерения этого параллелепипеда: A x B x , A y B y и A z B z
Из курса геометрии известно, что квадрат диагонали параллелепипеда равен сумме квадратов его измерений. Исходя из этого утверждения получим равенство: A B 2 = A x B x 2 + A y B y 2 + A z B z 2
Используя полученные ранее выводы, запишем следующее:
A x B x = x B - x A , A y B y = y B - y A , A z B z = z B - z A
Преобразуем выражение:
A B 2 = A x B x 2 + A y B y 2 + A z B z 2 = x B - x A 2 + y B - y A 2 + z B - z A 2 = = (x B - x A) 2 + (y B - y A) 2 + z B - z A 2
Итоговая формула для определения расстояния между точками в пространстве будет выглядеть следующим образом:
A B = x B - x A 2 + y B - y A 2 + (z B - z A) 2
Полученная формула действительна также для случаев, когда:
Точки совпадают;
Лежат на одной координатной оси или прямой, параллельной одной из координатных осей.
Примеры решения задач на нахождение расстояния между точками
Пример 1Исходные данные: задана координатная прямая и точки, лежащие на ней с заданными координатами A (1 - 2) и B (11 + 2) . Необходимо найти расстояние от точки начала отсчета O до точки A и между точками A и B .
Решение
- Расстояние от точки начала отсчета до точки равно модулю координаты этой точки, соответственно O A = 1 - 2 = 2 - 1
- Расстояние между точками A и B определим как модуль разности координат этих точек: A B = 11 + 2 - (1 - 2) = 10 + 2 2
Ответ: O A = 2 - 1 , A B = 10 + 2 2
Пример 2
Исходные данные: задана прямоугольная система координат и две точки, лежащие на ней A (1 , - 1) и B (λ + 1 , 3) . λ – некоторое действительное число. Необходимо найти все значения этого числа, при которых расстояние А В будет равно 5 .
Решение
Чтобы найти расстояние между точками A и B , необходимо использовать формулу A B = (x B - x A) 2 + y B - y A 2
Подставив реальные значения координат, получим: A B = (λ + 1 - 1) 2 + (3 - (- 1)) 2 = λ 2 + 16
А также используем имеющееся условие, что А В = 5 и тогда будет верным равенство:
λ 2 + 16 = 5 λ 2 + 16 = 25 λ = ± 3
Ответ: А В = 5 , если λ = ± 3 .
Пример 3
Исходные данные: задано трехмерное пространство в прямоугольной системе координат O x y z и лежащие в нем точки A (1 , 2 , 3) и B - 7 , - 2 , 4 .
Решение
Для решения задачи используем формулу A B = x B - x A 2 + y B - y A 2 + (z B - z A) 2
Подставив реальные значения, получим: A B = (- 7 - 1) 2 + (- 2 - 2) 2 + (4 - 3) 2 = 81 = 9
Ответ: | А В | = 9
Если вы заметили ошибку в тексте, пожалуйста, выделите её и нажмите Ctrl+Enter
Решение задач по математике у учащихся часто сопровождается многими трудностями. Помочь учащемуся справиться с этими трудности, а так же научить применять имеющиеся у него теоретические знания при решении конкретных задач по всем разделам курса предмета «Математика» – основное назначение нашего сайта.
Приступая к решению задач по теме , учащиеся должны уметь строить точку на плоскости по ее координатам, а так же находить координаты заданной точки.
Вычисление расстояния между взятыми на плоскости двумя точками А(х А; у А) и В(х В; у В), выполняется по формуле d = √((х А – х В) 2 + (у А – у В) 2) , где d – длина отрезка, который соединяет эти точки на плоскости.
Если один из концов отрезка совпадает с началом координат, а другой имеет координаты М(х М; у М), то формула для вычисления d примет вид ОМ = √(х М 2 + у М 2).
1. Вычисление расстояния между двумя точками по данным координатам этих точек
Пример 1 .
Найти длину отрезка, который соединяет на координатной плоскости точки А(2; -5) и В(-4; 3) (рис. 1).
Решение.
В условии задачи дано: х А = 2; х В = -4; у А = -5 и у В = 3. Найти d.
Применив формулу d = √((х А – х В) 2 + (у А – у В) 2), получим:
d = АВ = √((2 – (-4)) 2 + (-5 – 3) 2) = 10.
2. Вычисление координат точки, которая равноудалена от трех заданных точек
Пример 2.
Найти координаты точки О 1 , которая равноудалена от трех точек А(7; -1) и В(-2; 2) и С(-1; -5).
Решение.
Из формулировки условия задачи следует, что О 1 А = О 1 В = О 1 С. Пусть искомая точка О 1 имеет координаты (а; b). По формуле d = √((х А – х В) 2 + (у А – у В) 2) найдем:
О 1 А = √((а – 7) 2 + (b + 1) 2);
О 1 В = √((а + 2) 2 + (b – 2) 2);
О 1 С = √((а + 1) 2 + (b + 5) 2).
Составим систему из двух уравнений:
{√((а – 7) 2 + (b + 1) 2) = √((а + 2) 2 + (b – 2) 2),
{√((а – 7) 2 + (b + 1) 2) = √((а + 1) 2 + (b + 5) 2).
После возведения в квадрат левой и правой частей уравнений запишем:
{(а – 7) 2 + (b + 1) 2 = (а + 2) 2 + (b – 2) 2 ,
{(а – 7) 2 + (b + 1) 2 = (а + 1) 2 + (b + 5) 2 .
Упростив, запишем
{-3а + b + 7 = 0,
{-2а – b + 3 = 0.
Решив систему, получим: а = 2; b = -1.
Точка О 1 (2; -1) равноудалена от трех заданных в условии точек, которые не лежат на одной прямой. Эта точка – есть центр окружности, проходящей через три заданные точки (рис. 2) .
3. Вычисление абсциссы (ординаты) точки, которая лежит на оси абсцисс (ординат) и находится на заданном расстоянии от данной точки
Пример 3.
Расстояние от точки В(-5; 6) до точки А, лежащей на оси Ох равно 10. Найти точку А.
Решение.
Из формулировки условия задачи следует, что ордината точки А равна нулю и АВ = 10.
Обозначив абсциссу точки А через а, запишем А(а; 0).
АВ = √((а + 5) 2 + (0 – 6) 2) = √((а + 5) 2 + 36).
Получаем уравнение √((а + 5) 2 + 36) = 10. Упростив его, имеем
а 2 + 10а – 39 = 0.
Корни этого уравнения а 1 = -13; а 2 = 3.
Получаем две точки А 1 (-13; 0) и А 2 (3; 0).
Проверка:
А 1 В = √((-13 + 5) 2 + (0 – 6) 2) = 10.
А 2 В = √((3 + 5) 2 + (0 – 6) 2) = 10.
Обе полученные точки подходят по условию задачи (рис. 3).
4. Вычисление абсциссы (ординаты) точки, которая лежит на оси абсцисс (ординат) и находится на одинаковом расстоянии от двух заданных точек
Пример 4.
Найти на оси Оу точку, которая находится на одинаковом расстоянии от точек А(6; 12) и В(-8; 10).
Решение.
Пусть координаты нужной по условию задачи точки, лежащей на оси Оу, будут О 1 (0; b) (у точки, лежащей на оси Оу, абсцисса равна нулю). Из условия следует, что О 1 А = О 1 В.
По формуле d = √((х А – х В) 2 + (у А – у В) 2) находим:
О 1 А = √((0 – 6) 2 + (b – 12) 2) = √(36 + (b – 12) 2);
О 1 В = √((а + 8) 2 + (b – 10) 2) = √(64 + (b – 10) 2).
Имеем уравнение √(36 + (b – 12) 2) = √(64 + (b – 10) 2) или 36 + (b – 12) 2 = 64 + (b – 10) 2 .
После упрощения получим: b – 4 = 0, b = 4.
Необходимая по условию задачи точка О 1 (0; 4) (рис. 4).
5. Вычисление координат точки, которая находится на одинаковом расстоянии от осей координат и некоторой заданной точки
Пример 5.
Найти точку М, расположенную на координатной плоскости на одинаковом расстоянии от осей координат и от точки А(-2; 1).
Решение.
Необходимая точка М, как и точка А(-2; 1), располагается во втором координатном углу, так как она равноудалена от точек А, Р 1 и Р 2 (рис. 5) . Расстояния точки М от осей координат одинаковые, следовательно, ее координатами будут (-a; a), где а > 0.
Из условия задачи следует, что МА = МР 1 = МР 2 , МР 1 = а; МР 2 = |-a|,
т.е. |-a| = а.
По формуле d = √((х А – х В) 2 + (у А – у В) 2) находим:
МА = √((-а + 2) 2 + (а – 1) 2).
Составим уравнение:
√((-а + 2) 2 + (а – 1) 2) = а.
После возведения в квадрат и упрощения имеем: а 2 – 6а + 5 = 0. Решим уравнение, найдем а 1 = 1; а 2 = 5.
Получаем две точки М 1 (-1; 1) и М 2 (-5; 5), удовлетворяющие условию задачи.
6. Вычисление координат точки, которая находится на одинаковом заданном расстоянии от оси абсцисс (ординат) и от данной точки
Пример 6.
Найти точку М такую, что расстояние ее от оси ординат и от точки А(8; 6) будет равно 5.
Решение.
Из условия задачи следует, что МА = 5 и абсцисса точки М равна 5. Пусть ордината точки М равна b, тогда М(5; b) (рис. 6).
По формуле d = √((х А – х В) 2 + (у А – у В) 2) имеем:
МА = √((5 – 8) 2 + (b – 6) 2).
Составим уравнение:
√((5 – 8) 2 + (b – 6) 2) = 5. Упростив его, получим: b 2 – 12b + 20 = 0. Корни этого уравнения b 1 = 2; b 2 = 10. Следовательно, есть две точки, удовлетворяющие условию задачи: М 1 (5; 2) и М 2 (5; 10).
Известно, что многие учащиеся при самостоятельном решении задач нуждаются в постоянных консультациях по приемам и методам их решения. Зачастую, найти путь к решению задачи без помощи преподавателя учащемуся не под силу. Необходимые консультации по решению задач учащийся и может получить на нашем сайте.
Остались вопросы? Не знаете, как найти расстояние между двумя точками на плоскости?
Чтобы получить помощь репетитора – зарегистрируйтесь .
Первый урок – бесплатно!
сайт, при полном или частичном копировании материала ссылка на первоисточник обязательна.
Даны точек на плоскости, заданные своими координатами . Требуется найти среди них такие две точки, расстояние между которыми минимально:
Расстояния мы берём обычные евклидовы:
Тривиальный алгоритм — перебор всех пар и вычисление расстояния для каждой — работает за . Ниже описывается алгоритм, работающий за время . Этот алгоритм был предложен Препаратой (Preparata) в 1975 г. Препарата и Шамос также показали, что в модели дерева решений этот алгоритм асимптотически оптимален.
Алгоритм
Построим алгоритм по общей схеме алгоритмов "разделяй-и-властвуй" : алгоритм оформляем в виде рекурсивной функции, которой передаётся множество точек; эта рекурсивная функция разбивает это множество пополам, вызывает себя рекурсивно от каждой половины, а затем выполняет какие-то операции по объединению ответов. Операция объединения заключается в обнаружении случаев, когда одна точка оптимального решения попала в одну половину, а другая точка — в другую (в этом случае рекурсивные вызовы от каждой из половинок отдельно обнаружить эту пару, конечно, не смогут). Основная сложность, как всегда, заключается в эффективной реализации этой стадии объединения. Если рекурсивной функции передаётся множество из точек, то стадия объединения должна работать не более, чем , тогда асимптотика всего алгоритма будет находиться из уравнения:
Решением этого уравнения, как известно, является .
Итак, перейдём к построению алгоритма. Чтобы в будущем прийти к эффективной реализации стадии объединения, разбивать множество точек на два будем согласно их -координатам: фактически мы проводим некоторую вертикальную прямую, разбивающую множество точек на два подмножества примерно одинаковых размеров. Такое разбиение удобно произвести следующим образом: отсортируем точки стандартно как пары чисел, т.е.:
Тогда возьмём среднюю после сортировки точку (), и все точки до неё и саму отнесём к первой половине, а все точки после неё — ко второй половине:
Теперь, вызвавшись рекурсивно от каждого из множеств и , мы найдём ответы и для каждой из половинок. Возьмём лучший из них: .
Теперь нам надо произвести стадию объединения , т.е. попытаться обнаружить такие пары точек, расстояние между которыми меньше , причём одна точка лежит в , а другая — в . Очевидно, что для этого достаточно рассматривать только те точки, которые отстоят от вертикальной прямой раздела на расстояние, меньшее , т.е. множество рассматриваемых на этой стадии точек равно:
Для каждой точки из множества надо попытаться найти точки, находящиеся к ней ближе, чем . Например, достаточно рассматривать только те точки, координата которых отличается не более чем на . Более того, не имеет смысла рассматривать те точки, у которых -координата больше -координаты текущей точки. Таким образом, для каждой точки определим множество рассматриваемых точек следующим образом:
Если мы отсортируем точки множества по -координате, то находить будет очень легко: это несколько точек подряд до точки .
Итак, в новых обозначениях стадия объединения выглядит следующим образом: построить множество , отсортировать в нём точки по -координате, затем для каждой точки рассмотреть все точки , и каждой пары посчитать расстояние и сравнить с текущим наилучшим расстоянием.
На первый взгляд, это по-прежнему неоптимальный алгоритм: кажется, что размеры множеств будут порядка , и требуемая асимптотика никак не получится. Однако, как это ни удивительно, можно доказать, что размер каждого из множеств есть величина , т.е. не превосходит некоторой малой константы вне зависимости от самих точек. Доказательство этого факта приведено в следующем разделе.
Наконец, обратим внимание на сортировки, которых вышеописанный алгоритм содержит сразу две: сначала сортировка по парам (,), а затем сортировка элементов множества по . На самом деле, от обеих этих сортировок внутри рекурсивной функции можно избавиться (иначе бы мы не достигли оценки для стадии объединения, и общая асимптотика алгоритма получилась бы ). От первой сортировки избавиться легко — достаточно предварительно, до запуска рекурсии, выполнить эту сортировку: ведь внутри рекурсии сами элементы не меняются, поэтому нет никакой необходимости выполнять сортировку заново. Со второй сортировкой чуть сложнее, выполнить её предварительно не получится. Зато, вспомнив сортировку слиянием (merge sort), которая тоже работает по принципу разделяй-и-властвуй, можно просто встроить эту сортировку в нашу рекурсию. Пусть рекурсия, принимая какое-то множество точек (как мы помним, упорядоченное по парам ) возвращает это же множество, но отсортированное уже по координате . Для этого достаточно просто выполнить слияние (за ) двух результатов, возвращённых рекурсивными вызовами. Тем самым получится отсортированное по множество.
Оценка асимптотики
Чтобы показать, что вышеописанный алгоритм действительно выполняется за , нам осталось доказать следующий факт: .
Итак, пусть мы рассматриваем какую-то точку ; напомним, что множество — это множество точек, -координата которых лежит в отрезке , а, кроме того, по координате и сама точка , и все точки множества лежат в полосе шириной . Иными словами, рассматриваемые нами точки и лежат в прямоугольнике размера .
Наша задача — оценить максимальное количество точек, которое может лежать в этом прямоугольнике ; тем самым мы оценим и максимальный размер множества . При этом при оценке надо не забывать, что могут встречаться повторяющиеся точки.
Вспомним, что получалось как минимум из двух результатов рекурсивных вызовов — от множеств и , причём содержит точки слева от линии раздела и частично на ней, — оставшиеся точки линии раздела и точки справа от неё. Для любой пары точек из , равно как и из , расстояние не может оказаться меньше — иначе бы это означало некорректность работы рекурсивной функции.
Для оценки максимального количества точек в прямоугольнике разобьём его на два квадрата , к первому квадрату отнесём все точки , а ко второму — все остальные, т.е. . Из приведённых выше соображений следует, что в каждом из этих квадратов расстояние между любыми двумя точками не менее .
Покажем, что в каждом квадрате не более четырёх точек. Например, это можно сделать следующим образом: разобьём квадрат на 4 подквадрата со сторонами . Тогда в каждом из этих подквадратов не может быть больше одной точки (т.к. даже диагональ равна , что меньше ). Следовательно, во всём квадрате не может быть более 4 точек.
Итак, мы доказали, что в прямоугольнике не может быть больше точек, а, следовательно, размер множества не может превосходить , что и требовалось доказать.
Реализация
Введём структуру данных для хранения точки (её координаты и некий номер) и операторы сравнения, необходимые для двух видов сортировки:
struct pt { int x, y, id; } ; inline bool cmp_x (const pt & a, const pt & b) { return a.x < b.x || a.x == b.x && a.y < b.y ; } inline bool cmp_y (const pt & a, const pt & b) { return a.y < b.y ; } pt a[ MAXN] ;Для удобной реализации рекурсии введём вспомогательную функцию , которая будет вычислять расстояние между двумя точками и проверять, не лучше ли это текущего ответа:
double ; int ansa, ansb; inline void upd_ans (const pt & a, const pt & b) { double dist = sqrt ((a.x - b.x ) * (a.x - b.x ) + (a.y - b.y ) * (a.y - b.y ) + .0 ) ; if (dist < ) = dist, ansa = a.id , ansb = b.id ; }Наконец, реализация самой рекурсии. Предполагается, что перед её вызовом массив уже отсортирован по -координате. Рекурсии передаётся просто два указателя , , которые указывают, что она должна искать ответ для . Если расстояние между и слишком мало, то рекурсию надо остановить, и выполнить тривиальный алгоритм поиска ближайшей пары и затем отсортировать подмассив по -координате.
Для слияния двух множеств точек, полученных от рекурсивных вызовов, в одно (упорядоченное по -координате), мы используем стандартную функцию STL , и создаём вспомогательный буфер (один на все рекурсивные вызовы). (Использовать нецелесообразно, т.к. она в общем случае работает не за линейное время).
Наконец, множество хранится в том же массиве .
void rec (int l, int r) { if (r - l <= 3 ) { for (int i= l; i<= r; ++ i) for (int j= i+ 1 ; j<= r; ++ j) upd_ans (a[ i] , a[ j] ) ; sort (a+ l, a+ r+ 1 , & cmp_y) ; return ; } int m = (l + r) >> 1 ; int midx = a[ m] .x ; rec (l, m) , rec (m+ 1 , r) ; static pt t[ MAXN] ; merge (a+ l, a+ m+ 1 , a+ m+ 1 , a+ r+ 1 , t, & cmp_y) ; copy (t, t+ r- l+ 1 , a+ l) ; int tsz = 0 ; for (int i= l; i<= r; ++ i) if (abs (a[ i] .x - midx) < ) { for (int j= tsz- 1 ; j>= 0 && a[ i] .y - t[ j] .y < ; -- j) upd_ans (a[ i] , t[ j] ) ; t[ tsz++ ] = a[ i] ; } }Кстати говоря, если все координаты целые, то на время работы рекурсии можно вообще не переходить к дробным величинам, и хранить в квадрат минимального расстояния.
