Найти номера двух точек, расстояние между которыми наибольшее

@EvgenyGo · Регистрация: 08.12.2016

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

Даны координаты N точек на плоскости x(0), y(0) ,..., x(n), y(n) (N=20).
Найти номера двух точек, расстояние между которыми наибольшее
(считать, что такая пара точек единственная).

@Tsin · 08.12.2016, 18:32

За O(N^2) легко. Быстрее - надо думать.

C#

using System;
 
class Program
{
    struct Point
    {
        public float X;
        public float Y;
 
        public override string ToString() { return "[" + X + ", " + Y + "]"; }
 
        public double DistTo(Point other)
        {
            var res = Math.Sqrt((this.X - other.X) * (this.X - other.X) + (this.Y - other.Y) * (this.Y - other.Y));
            return res;
        }
    }
 
    static Random R = new Random();
 
    static void Main()
    {
        int N = 5;
        Point[] array = new Point[N];
        for (int i = 0; i < N; i++)
            array[i] = new Point() { X = R.Next(100), Y = R.Next(100) };
 
        Console.WriteLine(String.Join(" ", array));
 
        double maxDist = 0;
        int[] idx = new int[2];
        for (int i = 0; i < N - 1; i++)
        {
            for (int j = i + 1; j < N; j++)
            {
                var dist = array[i].DistTo(array[j]);
                if (dist > maxDist)
                {
                    maxDist = dist;
                    idx[0] = i;
                    idx[1] = j;
                }
            }
        }
 
        Console.WriteLine(String.Format("Dist(array[{0}], array[{1}]) = {2}", idx[0], idx[1], maxDist));
    }
}

@OwenGlendower · 12.12.2016, 22:31

EvgenyGo, допустим что координаты точек находятся в массиве points. Объявляем переменные idx1, idx2 типа int и переменную maxDistance типа double. Инициализируем maxDistance отрицательным числом. Делаем цикл for по i от 0 до длины массива points. Внутри него вложенный цикл for по j от i+1 до длины массива points. Внутри вычисляем расстояние между точками с индексами i, j и получаем абсолютное значение (Math.Abs). Если она больше максимальной, то запоминаем i, j в idx1, idx2. Расстояние записываем в maxDistance. После циклов печатаем значения переменных idx1, idx2.

@EvgenyGo · 17.12.2016, 22:25 **[ТС]**

Очень сложный код, а можно попроще немного ? )

@bax_tang · 19.12.2016, 22:09

EvgenyGo, эм... а в чём он сложный-то?

@Diamante · 20.12.2016, 00:12

Не по теме:

bax_tang, имхо, сложность состоит в том, что это код, который надо понимать, а не ОДНА ЕДИНСТВЕННАЯ КНОПКА "СДЕЛАТЬ ~~ЗАЕ~~ КАК МНЕ НАДО!!11разраз"

@EvgenyGo · 21.12.2016, 00:15 **[ТС]**

C#

using System;
 
namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random();
            double d = 0;
            int[] a = new int[20];
            int[] b = new int[20];
            for (int i = 0; i < 20; ++i)
            {
                for (int j = 0; j < 20; ++j)
                {
                    a[i] = random.Next(10, 99);
                    b[j] = random.Next(10, 99);
                }
            }
            Console.WriteLine("Исходный массив:");
            Console.WriteLine();
            Console.Write("x: ");
            for (int i = 0; i < 20; ++i)
            {
                {      
                   Console.Write(" "+ a[i]);
                }             
            }
            Console.WriteLine();
            Console.Write("y: ");
            for (int j = 0; j < 20; ++j)
            {             
                {
                    Console.Write(" " + b[j]);
                }      
            }
            Console.WriteLine();
 
 
            int max1 = a[0];
            for (int i = 0; i < 20; ++i) 
                if (a[i] > max1)
                    max1 = a[i];
 
            int max2 = b[0];
            for (int j= 0; j < 20; ++j) 
                if (b[j] > max2)
                    max2 = b[j];
 
 
 
            Console.WriteLine("Максимальный элемент x= " + max1); 
            Console.WriteLine("Максимальный элемент y= " + max2);
 
            d = max1 + max2;
            Console.WriteLine("Расстояние между максимальными точками " + d);
            Console.Read();
 
            
        }
 
    }
}

Ввел я 2а одномерных массива, а.b
Присвоил им рандомные значения, нашел в каждом массиве одномерный массив

Дальше нужно узнать по формуле это расстояние
Преподаватель дал мне формулу:

d=abs(x2-x1)^2+(y2-y1)^2
Формула для расчета длины.
Такой вопрос, где мне взять этот х1 и х2 и у1 и у2

@OwenGlendower · 21.12.2016, 00:35

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

Ввел я 2а одномерных массива, а.b

А назвал бы ты их x и y и вопрос "где взять координаты" не возник бы.

@EvgenyGo · 28.12.2016, 01:55 **[ТС]**

C#

using System;
namespace ConsoleApplication5
{
    class Program
    {
        static void Main(string[] args)
        {
            Random random = new Random();
            int n = 20;
            double n1 = 0;
            double n2 = 0;
            double result = 0;
            double[] x = new double[n];
            double[] y = new double[n];
            for (int i = 0; i < n; ++i)
            {
                for (int j = 0; j < n; ++j)
                {
                    x[i] = random.Next(-99, 99);
                    y[j] = random.Next(-99, 99);
                }
            }
                        Console.WriteLine("Исходный массив:");
            Console.WriteLine();
            Console.Write("x: ");
            for (int i = 0; i < n; ++i)
            {
                {      
                   Console.Write(" "+ x[i]);
                }             
            }
            Console.WriteLine();
            Console.Write("y: ");
            for (int j = 0; j < n; ++j)
            {             
                {
                    Console.Write(" " + y[j]);
                }      
            }
 
 
 
            for (int i = 1;  i < n; i++)
            {
 
                double tmp1 = Math.Pow((x[i]) - (x[i-1]), 2);
                double tmp2 = Math.Pow((y[i]) - (y[i-1]), 2);
                double tmp = Math.Sqrt(tmp1 + tmp2);
                if (tmp > result)
                {
                    result = tmp;
                    n1 = x[i];
                    n2 = y[i];
                }
 
            }
            Console.WriteLine();
 
            Console.WriteLine("Максимальное число по оси x = " + n1);
            Console.WriteLine("Максимальное число по оси y = " + n2);
           
            Console.WriteLine("Результат = " + result);
 
                Console.ReadKey();
            }
        }
    }

Даны координаты N точек на плоскости x(0), y(0) ,..., x(n), y(n) (N=20).
Найти номера двух точек, расстояние между которыми наибольшее
(считать, что такая пара точек единственная).

Как вывести чтобы он выводил индексы точек, а не сами числа?

@ata · 28.12.2016, 02:31

C#

using System;
using System.Linq;
 
class Program
{
    class Point
    {
        public readonly int Index;
        public readonly double X;
        public readonly double Y;
 
        public Point(int index, double x, double y)
        {
            Index = index;
            X = x;
            Y = y;
        }
 
        public double Distance(Point other)
        {
            double dx = X - other.X;
            double dy = Y - other.Y;
            return Math.Sqrt(dx * dx + dy * dy);
        }
 
        public override string ToString()
        {
            return String.Format("Point {0}: X = {1}; Y = {2}", Index, X, Y);
        }
    }
 
    class Line
    {
        public readonly Point A;
        public readonly Point B;
        public readonly double Length;
 
        public Line(Point a, Point b)
        {
            A = a;
            B = b;
            Length = a.Distance(b);
        }
    }
 
    static void Main()
    {
        Random rnd = new Random();
        Point[] points = Enumerable.Range(0, 20)
            .Select(i => new Point(i, rnd.NextDouble() * 200.0 - 100.0, rnd.NextDouble() * 200.0 - 100.0))
            .ToArray();
        foreach (Point p in points)
        {
            Console.WriteLine(p);
        }
        Line maxLine = null;
        for (int i = 0; i < points.Length - 1; i++)
        {
            for (int j = i + 1; j < points.Length; j++)
            {
                Line curLine = new Line(points[i], points[j]);
                if (maxLine == null || curLine.Length > maxLine.Length)
                {
                    maxLine = curLine;
                }
            }
        }
        Console.WriteLine(maxLine.A.Index);
        Console.WriteLine(maxLine.B.Index);
        Console.WriteLine(maxLine.Length);
    }
}

@EvgenyGo · 28.12.2016, 02:44 **[ТС]**

Мне не нужен чужой код, помогите мне лучше в моем

@pycture · 28.12.2016, 08:32

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

Мне не нужен чужой код, помогите мне лучше в моем

от строки 43 и ниже

C#

for (int j = 0; j < n - 1; j++)
    for (int i = j + 1; i < n; i++)
    {
        double tmp1 = Math.Pow((x[i]) - (x[j]), 2);
        double tmp2 = Math.Pow((y[i]) - (y[j]), 2);
        double tmp = Math.Sqrt(tmp1 + tmp2);
        if (tmp > result)
        {
            result = tmp;
            n1 = i;
            n2 = j;
        }
    }
Console.WriteLine();
 
Console.WriteLine("Номер точки 1 = " + n1);
Console.WriteLine("Номер точки 2 = " + n2);
 
Console.WriteLine("Результат = " + result);
 
Console.ReadKey();

@EvgenyGo 0 / 0 / 0 Регистрация: 08.12.2016 Сообщений: 25
		1
	Найти номера двух точек, расстояние между которыми наибольшее 08.12.2016, 17:48. Показов 2013. Ответов 11 Метки нет (Все метки) Даны координаты N точек на плоскости x(0), y(0) ,..., x(n), y(n) (N=20). Найти номера двух точек, расстояние между которыми наибольшее (считать, что такая пара точек единственная). 0

@OwenGlendower Администратор 17709 / 13836 / 5313 Регистрация: 17.03.2014 Сообщений: 28,343 Записей в блоге: 1
	12.12.2016, 22:31	3
	EvgenyGo, допустим что координаты точек находятся в массиве points. Объявляем переменные idx1, idx2 типа int и переменную maxDistance типа double. Инициализируем maxDistance отрицательным числом. Делаем цикл for по i от 0 до длины массива points. Внутри него вложенный цикл for по j от i+1 до длины массива points. Внутри вычисляем расстояние между точками с индексами i, j и получаем абсолютное значение (Math.Abs). Если она больше максимальной, то запоминаем i, j в idx1, idx2. Расстояние записываем в maxDistance. После циклов печатаем значения переменных idx1, idx2. 0

@EvgenyGo 0 / 0 / 0 Регистрация: 08.12.2016 Сообщений: 25
	17.12.2016, 22:25 [ТС]	4
	Очень сложный код, а можно попроще немного ? ) 0

@bax_tang .NET senior 441 / 359 / 137 Регистрация: 23.09.2016 Сообщений: 980
	19.12.2016, 22:09	5
	EvgenyGo, эм... а в чём он сложный-то? 0

@Diamante
	20.12.2016, 00:12 #6
	Не по теме: bax_tang, имхо, сложность состоит в том, что это код, который надо понимать, а не ОДНА ЕДИНСТВЕННАЯ КНОПКА "СДЕЛАТЬ ~~ЗАЕ~~ КАК МНЕ НАДО!!11разраз" 0

@OwenGlendower Администратор 17709 / 13836 / 5313 Регистрация: 17.03.2014 Сообщений: 28,343 Записей в блоге: 1
	21.12.2016, 00:35	8
	Сообщение от EvgenyGo Ввел я 2а одномерных массива, а.b А назвал бы ты их `x` и `y` и вопрос "где взять координаты" не возник бы. 0

@EvgenyGo 0 / 0 / 0 Регистрация: 08.12.2016 Сообщений: 25
	28.12.2016, 02:44 [ТС]	11
	Мне не нужен чужой код, помогите мне лучше в моем 0

	28.12.2016, 08:32