e-olymp 555. Ближайшие точки

ML25. Расстояние между двумя точками

ML18

Задача ML18

C++ для приматов

Tag Archives: расстояние между двумя точками

e-olymp 555. Ближайшие точки

ML25. Расстояние между двумя точками

ML18

Задача ML18

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Задача

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

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

Тесты

Решение

Объяснение

Related Images:

Related Images:

Условие задачи

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

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

Тестирование

Реализация

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

Задача

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

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

Тесты

Решение

Объяснение

Related Images:

Related Images:

Условие задачи

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

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

Тестирование

Реализация

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

Related Images:

30/03/2019 by Кирилл Веремйов

Антон в школе начал изучать математику. Его внимание привлекло новое для него понятие числовой прямой. Антон быстро научился вычислять расстояния между двумя точками на этой прямой, задавать отрезки и интервалы на ней.

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

Требуется написать программу, которая поможет Антону решить поставленную задачу.

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

В первой строке вывести минимальное расстояние между двумя заданными точками. Во второй строке вывести номера точек, которым соответствует найденное расстояние. Точки нумеруются натуральными числами от $1$ до $n$ в том же порядке, в котором они заданы во входе. Если ответов несколько, выведите любой из них.

Входные данные	Выходные данные
5 10 3 6 2 5	1 2 4
6 10 3 6 1 5 11	1 3 5
9 14545690 4343 -6 10 500 1100 -1 2 10	0 4 9
2 1 5	4 2 1
2 -1000000000 1000000000	2000000000 2 1
9 1 5 9 15 3 100 -1 4 10	1 8 5
10 0 1 5 10 20 100 120 250 -100 55	1 2 1

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

int main() {
    long long n;
    cin >> n;
    map<long long, long long> Ox;
    long long dis = 0,A = 0,B = 0;//dis- distance
    bool zero_dis = 0;
    for(long long i = 1;i <= n && !zero_dis;i++){
        long long tmp;
        cin >> tmp;
        if(Ox[tmp] != 0){
            zero_dis = true;
            A = Ox[tmp];
            B = i;
            dis = 0;
        }
        else Ox[tmp] = i;
    }
    
    if(!zero_dis){
        dis = -1;
        for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){
            long long tmp_dis = j->first - i->first;
            if(dis>tmp_dis || dis<0){
                dis = tmp_dis;
                A = j->second;
                B = i->second;
            }
        }
    }
    cout << dis << "\n" << A << " " << B;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

long long n;

cin >> n;

map<long long, long long> Ox;

long long dis = 0,A = 0,B = 0;//dis- distance

bool zero_dis = 0;

for(long long i = 1;i <= n && !zero_dis;i++){

long long tmp;

cin >> tmp;

if(Ox[tmp] != 0){

zero_dis = true;

A = Ox[tmp];

B = i;

dis = 0;

}

else Ox[tmp] = i;

}

if(!zero_dis){

dis = -1;

for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){

long long tmp_dis = j->first - i->first;

if(dis>tmp_dis || dis<0){

dis = tmp_dis;

A = j->second;

B = i->second;

}

cout << dis << "\n" << A << " " << B;

return 0;

}

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации

e-olymp

ideone

26/09/2016 by Иванна Ялымова

Задача

Вычислить расстояние между двумя точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по известным координатам.

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

Координаты: [latex]x_a, y_a, z_a, x_b, y_b, z_b[/latex].

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

[latex]|AB|[/latex] — расстояние между точками [latex]A[/latex] и [latex]B[/latex].

Тесты

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

Код программы на С++

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

int main() {
    double xa, xb, ya, yb, za, zb;
    cin >> xa >> xb >> ya >> yb >> za >> zb;//вводим наши координаты
    double AB = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
    cout << AB;//выводим полученное расстояние
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double xa, xb, ya, yb, za, zb;

cin >> xa >> xb >> ya >> yb >> za >> zb;//вводим наши координаты

double AB = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));

cout << AB;//выводим полученное расстояние

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double xa, ya, za, xb, yb, zb;
        Scanner in = new Scanner(System.in);
        
        xa = in.nextDouble();
        ya = in.nextDouble();
        za = in.nextDouble();
        xb = in.nextDouble();
        yb = in.nextDouble();
        zb = in.nextDouble();
        
        double AB = Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
        
        System.out.println(AB);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double xa, ya, za, xb, yb, zb;

Scanner in = new Scanner(System.in);

xa = in.nextDouble();

ya = in.nextDouble();

za = in.nextDouble();

xb = in.nextDouble();

yb = in.nextDouble();

zb = in.nextDouble();

double AB = Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));

System.out.println(AB);

}

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

Вычисляем [latex]|AB|[/latex] между точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по такой формуле : [latex]|AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2}[/latex] и получаем результаты.

Ссылка: Условие задачи
Ссылка: Решение задачи на сайте Ideone.com (C++)
Ссылка: Решение задачи на сайте Ideone.com (Java)

28/09/2015 by Кудымовская Вика

Найти периметр треугольника по заданным координатам вершин [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex].

В одной строке заданы 9 чисел [latex]x_1, x_2, x_3, y_1, y_2, y_3, z_1, z_2, z_3[/latex] — координаты вершин треугольника [latex]ABC[/latex], значения которых не превышают по модулю [latex]100[/latex].

Вывести периметр [latex]p[/latex] данного треугольника.

Также условие задачи можно посмотреть здесь.

№	Входные данные ([latex]x_i, y_j, z_k; i, j, k= 1, 2, 3 [/latex])	Выходные данные
1	2 2 5 1 0 -1 3 5 10	16.0261556346
2	1 4 5 3 6 0 10.5 -2 -1	31.9047289894
3	15 26 13 32 18 56 80 0 -6.2	212.0962807371
4	-13 68 44 99 -100 70 0 2 1	450.5748518262
5	100 9 17 18 29 88 65 -16 0.36	310.4318979186

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main ()
{
	double x1, x2, x3, y1, y2, y3, z1, z2, z3;
	long double a, b, c, p;
	//стороны AB, BC, AC треугольника ABC обозначим 
	//соответственно, используя переменные a, b, c
	//используем значения переменных с плавающей точкой
	cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;
	a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));
	b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));
	c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));
	p= a + b + c;
	//вычисляем периметр 
	cout << fixed << setprecision(10) << p << endl;
	//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main ()

{

double x1, x2, x3, y1, y2, y3, z1, z2, z3;

long double a, b, c, p;

//стороны AB, BC, AC треугольника ABC обозначим

//соответственно, используя переменные a, b, c

//используем значения переменных с плавающей точкой

cin >> x1 >> x2 >> x3 >> y1 >> y2 >> y3 >> z1 >> z2 >> z3;

a= sqrt((x2-x1) * (x2-x1) + (y2-y1) * (y2-y1) + (z2-z1) * (z2-z1));

b= sqrt((x3-x2) * (x3-x2) + (y3-y2) * (y3-y2) + (z3-z2) * (z3-z2));

c= sqrt((x3-x1) * (x3-x1) + (y3-y1) * (y3-y1) + (z3-z1) * (z3-z1));

p= a + b + c;

//вычисляем периметр

cout << fixed << setprecision(10) << p << endl;

//выводим периметр треугольника с точностью до 10 (включительно) знаков после запятой

return 0;

}

Задан произвольный треугольник [latex]ABC[/latex] с такими координатами вершин: [latex]A(x_1,y_1,z_1)[/latex], [latex]B(x_2,y_2,z_2)[/latex] и [latex]C(x_3,y_3,z_3)[/latex]. Обозначим стороны треугольника [latex] AB, BC, AC[/latex] как [latex]a, b, c[/latex] соответственно.
Очевидно, что для того, чтобы вычислить периметр данного треугольника, нужно найти длины его сторон. Для этого воспользуемся формулой вычисления расстояния между двумя точками в пространстве. Получаем:[latex]a=\sqrt {(x_2-x_1)^2 + (y_2-y_1)^2 + (z_2-z_1)^2}[/latex]; [latex]b= \sqrt {(x_3-x_2)^2 + (y_3-y_2)^2 + (z_3-z_2)^2}[/latex]; [latex]c= \sqrt {(x_3-x_1)^2 + (y_3-y_1)^2 + (z_3-z_1)^2} [/latex].
Зная значения сторон треугольника, вычисляем периметр, используя формулу. Получаем: [latex]p= a + b + c[/latex].

Подробнее о декартовой системе координат можно прочесть здесь.

Для запроса на выполнение следует перейти по ссылке.

[latex]x_a[/latex]

[latex]y_a[/latex]

[latex]z_a[/latex]

[latex]x_b[/latex]

[latex]y_b[/latex]

[latex]z_b[/latex]

[latex]|AB|[/latex]