Найти две наиболее удаленные друга от друга точки в заданном множестве точек

@kalinkinan · Регистрация: 12.01.2015

Студворк — интернет-сервис помощи студентам

Координаты n точек на плоскости заданы в виде двумерного массива K[l..n,1..2]. Найти номера двух точек, расстояние между которыми наибольшее. Вычисление расстояния между двумя точками организовать в подпрограмме.

@AlexM24 · 23.01.2015, 17:42

Смысл программы прост:
1. Находим максимально удаленную точку, это будет первая точка
2. от этой точки считаем длинны отрезков к другим и находим самый длинный отрезок
3 к какой точке отрезок будет самым длинным то эта точка будет второй!

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

C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
#include <math.h>
main (){
int i=0,j=0,n,first_point,second_point;
float x,y,max=0,L=0;
scanf ("%d",&n);     
float K[n][2];// n-кол во строк (точек), 2 - кол во столбцов (1 столб-координата x, 2 столб-координата y)
while (i<n){
      scanf ("%f %f",&K[i][0],&K[i][1]);
      i++;
      }
//выводим точки на экран
i=0;
while (i<n){
      printf ("point %d (%f,%f)\n",i,K[i][0],K[i][1]);
      i++;
      }
//
 
// находим наиболее удаленную точку
i=0;
while (i<n){
      while (j<2){
            if (fabs(K[i][j])>=fabs(max)) {max=fabs(K[i][j]);first_point=i;}
            j++;
            }
            j=0;
      i++;
      }
      x=K[first_point][0];
      y=K[first_point][1];
//находим максимальную длинну отрезка от этой точки до остальных
i=0;
while (i<n){
      if (L<sqrt(powf(x-K[i][0],2)+powf(y-K[i][1],2))) {L=sqrt(powf(x-K[i][0],2)+powf(y-K[i][1],2)); second_point=i;}
      i++;
      }
//
printf ("first_point=%d,second_point=%d",first_point,second_point);// выводим индексы точек
getchar ();getchar ();
}

zer0mail · 24.01.2015, 12:41

Фигня, а не алгоритм. Что он посчитает для точек (0,8), (8,0), (9,9) ?

@Kerry_Jr · 24.01.2015, 12:53

Сообщение от AlexM24

Находим максимально удаленную точку, это будет первая точка

Откуда такая уверенность?

Добавлено через 5 минут

Сообщение от AlexM24

C++
1
2
scanf ("%d",&n);
float K[n][2];

такая штука только в GNU-компиляторах прокатит, и то не факт. Размер массива должен быть известен во время компиляции.

@AlexM24 · 24.01.2015, 14:04

Отвечаю сразу на оба предыдущих поста. См.скрин.

Найти две наиболее удаленные друга от друга точки в заданном множестве точек

Из скрина видно, что из точек (0,8) (8,0) (9,9) в качестве 1 точки будет (9,9) а вторая (поскольку точки равноудалены от первой) будет первая из введенных в Вашем примере.
И как тоже видно из скрина программа нормально компилится под виндой.

zer0mail · 24.01.2015, 14:14

Сообщение от AlexM24

в качестве 1 точки будет (9,9)

А максимальное расстояние на самом деле между (0,8) и (8,0) и точка (9,9) не при чем

@AlexM24 · 24.01.2015, 14:20

zer0mail - Молодец! Тогда остается перебирать все расстояния от всех точек!

@1XPLoade1 · 24.01.2015, 14:53

А вот так пробовали ?!?!:

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <stdio.h>
#include <conio.h>
#include <math.h>
 
#define N 5
 
double distance(int x1, int y1, int x2, int y2)
{
    return sqrt(pow((double)abs(x1 - x2), 2) + pow((double)abs(y1 - y2), 2));
}
 
int main(int argc, char* argv[])
{
    int M[N][2] = { { 3, 2 },
                    { 6, 4 },
                    { 1, 3 },
                    { 9, 1 },
                    { 7, 6 } };
 
    double max_dist = 0.00;
    int max_i = 0, max_j = max_i;
    for (int i = 0; i < N; i++)
        for (int j = i + 1; j < N; j++)
        {
            double d = distance(M[i][0], M[i][1], M[j][0], M[j][1]);
            if (d > max_dist || max_dist == 0.00)
            {
                max_dist = d;
                max_i = i; max_j = j;
            }
        }
 
    printf("(%d,%d) <--> (%d,%d) distance = %lf\n", 
        M[max_i][0],M[max_i][1], M[max_j][0], M[max_j][1], max_dist);
 
    _getch();
 
    return 0;
}

http://codepad.org/utket4Jd

@AlexM24 · 27.01.2015, 14:06

Нашел сайт от всех проблем! Ваш алгоритм по этой ссылке
http://e-maxx.ru/algo/nearest_points

Новые блоги и статьи Все статьи Все блоги /
Мысли в слух. Про "навсегда". kumehtar 16.04.2026 Подумалось тут, что наверное очень глупо использовать во всяких своих установках понятие "навсегда". Это очень сильное понятие, и я только начинаю понимать край его смысла, не смотря на то что давно. . .	My Business CRM MaGz GoLd 16.04.2026 Всем привет, недавно возникла потребность создать CRM, для личных нужд. Собственно программа предоставляет из себя базу данных клиентов, в которой можно фиксировать звонки, стадии сделки, а также. . .	Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .

@kalinkinan 0 / 0 / 0 Регистрация: 12.01.2015 Сообщений: 7

	Найти две наиболее удаленные друга от друга точки в заданном множестве точек 23.01.2015, 00:47. Показов 10726. Ответов 8 Метки нет (Все метки) Координаты n точек на плоскости заданы в виде двумерного массива K[l..n,1..2]. Найти номера двух точек, расстояние между которыми наибольшее. Вычисление расстояния между двумя точками организовать в подпрограмме. 0

zer0mail 2688 / 2260 / 244 Регистрация: 03.07.2012 Сообщений: 8,231 Записей в блоге: 1
	24.01.2015, 12:41
	Фигня, а не алгоритм. Что он посчитает для точек (0,8), (8,0), (9,9) ? 0

@AlexM24 11 / 11 / 11 Регистрация: 09.12.2014 Сообщений: 89
	24.01.2015, 14:04
	Отвечаю сразу на оба предыдущих поста. См.скрин. Из скрина видно, что из точек (0,8) (8,0) (9,9) в качестве 1 точки будет (9,9) а вторая (поскольку точки равноудалены от первой) будет первая из введенных в Вашем примере. И как тоже видно из скрина программа нормально компилится под виндой. 0

@AlexM24 11 / 11 / 11 Регистрация: 09.12.2014 Сообщений: 89
	24.01.2015, 14:20
	zer0mail - Молодец! Тогда остается перебирать все расстояния от всех точек! 0

@AlexM24 11 / 11 / 11 Регистрация: 09.12.2014 Сообщений: 89
	27.01.2015, 14:06
	Нашел сайт от всех проблем! Ваш алгоритм по этой ссылке http://e-maxx.ru/algo/nearest_points 0