VPF::[Visual С++] Найти точки - Форум программистов

Ambition

Дата 12.10.2006, 13:04 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.10.2006

Репутация: нет
Всего: нет

Привет, народ. Подскажите кодик задачки smile

Условие задания:
На плоскасти заданы своими целочисленными координатами n точек. Найти всевозможные группы по 3,4,... точки, лежащие на одной прямой.

ivashkanet

Дата 12.10.2006, 13:23 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149

Ambition, я представляю себе только пербор (ну с незначительными модификациями) smile

.
Если надо, могу накатать.

P.S. А VS --- это какой язык?

--------------------

design, simplicity, and experience with a technology focus

Ambition

Дата 12.10.2006, 13:25 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.10.2006

Репутация: нет
Всего: нет

Visual Studio (C++)

ivashkanet

Дата 12.10.2006, 13:34 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149

Ambition, могу алгоритм перебора наклепать для VS (C#) потом "обработаешь напильником" пойдет?

--------------------

design, simplicity, and experience with a technology focus

Ambition

Дата 12.10.2006, 14:20 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.10.2006

Репутация: нет
Всего: нет

ок, пойдёт

ivashkanet

Дата 12.10.2006, 14:55 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149

Наклепал.

Код


  class Program
    {
        struct Dot
        {
            public float X;
            public float Y;
            public Dot(float x, float y)
            {
                this.X = x;
                this.Y = y;
            }
        }

        static void Main(string[] args)
        {
            Dot[] dots = new Dot[10];
            dots[0] = new Dot(0, 0);
            dots[1] = new Dot(1, 2);
            dots[2] = new Dot(3, 4);
            dots[3] = new Dot(2, 4);
            dots[4] = new Dot(15, 20);
            dots[5] = new Dot(4, 36);
            dots[6] = new Dot(4, 11);
            dots[7] = new Dot(22, 19);
            dots[8] = new Dot(16, 32);
            dots[9] = new Dot(-56, -356);

            findDotsOnLine(dots);

            System.Console.ReadKey();
        }

        private static void findDotsOnLine(Dot[] dots)
        {
            int dotsCount = dots.Length;

            for (int i = 0; i < dotsCount; i++)
            {
                Dot startLineDot = dots[i];

                for (int j = i + 1; j < dotsCount; j++)
                {
                    // У прямой есть направляющий вектор (a, b) если по точкам, то 
                    // Если у двух прямых направляющие векторы совпадают (по направлению)
                    // то прямые паралельны, но в нашем случае они выходят из одной 
                    // точки (startLineDot) и поэтому обязаны совпасть,
                    // а значит третья точка лежит на одной прямой с первыми двумя
                    // так как нам важно только направление, то будем проверять условие
                    // a1 * b2 - b1 *a2 = 0

                    // Тута будем складывать точки лежащие на одной прямой с 
                    // i-ой и j-ой точками
                    Dot[] foundedDots = new Dot[dotsCount];
                    int foundedDotsCounter = 0;

                    float a1 = dots[j].X - startLineDot.X;
                    float b1 = dots[j].Y - startLineDot.Y;

                    for (int k = j + 1; k < dotsCount; k++)
                    {
                        float a2 = dots[k].X - startLineDot.X;
                        float b2 = dots[k].Y - startLineDot.Y;

                        if (a1 * b2 - b1 * a2 == 0)
                        {
                            // точка наша, добавляем ее в массив найденных
                            foundedDots[foundedDotsCounter] = dots[k];
                            foundedDotsCounter += 1;
                        }
                    }

                    // Если мы нашли хоть одну "третью" точку --- показываем массив точек
                    if (foundedDotsCounter > 0)
                    {
                        System.Console.Write("({0}, {1}), ", dots[i].X, dots[i].Y);
                        System.Console.Write("({0}, {1}), ", dots[j].X, dots[j].Y);

                        for (int l = 0; l < foundedDotsCounter; l++)
                        {
                            System.Console.Write("({0}, {1}), ", foundedDots[l].X, foundedDots[l].Y);
                        }
                        System.Console.WriteLine();
                    }
                }
            }
        }
    }

Правда есть маленький (но очень неприятный) недостаток.
Если у нас есть более четырех точек заведомо лежащих на одной прямой, то они появятся более чем один раз smile

Было бы неплохо удалять их, но массив не позволяет это делать. Может в С++ есть что-нибудь типа коллекций? Тогда было бы лучше smile

P.S. Пока буду помечать их (ставить в заведомо "невозможное значение" либо завести в структуре Dot флаг smile

Не знаю)

Добавлено @ 15:01
Вот так лучше, но некрасивее smile

Код


   class Program
    {
        struct Dot
        {
            public float X;
            public float Y;
            public Dot(float x, float y)
            {
                this.X = x;
                this.Y = y;
            }
        }

        static void Main(string[] args)
        {
            Dot[] dots = new Dot[10];
            dots[0] = new Dot(0, 0);
            dots[1] = new Dot(1, 2);
            dots[2] = new Dot(3, 4);
            dots[3] = new Dot(2, 4);
            dots[4] = new Dot(15, 20);
            dots[5] = new Dot(4, 36);
            dots[6] = new Dot(4, 11);
            dots[7] = new Dot(22, 19);
            dots[8] = new Dot(16, 32);
            dots[9] = new Dot(-56, -356);

            findDotsOnLine(dots);

            System.Console.ReadKey();
        }

        private static void findDotsOnLine(Dot[] dots)
        {
            Dot impossibleDot = new Dot(float.MinValue, float.MaxValue);

            int dotsCount = dots.Length;

            for (int i = 0; i < dotsCount; i++)
            {
                if (dots[i].X == impossibleDot.X && dots[i].Y == impossibleDot.Y) continue;

                Dot startLineDot = dots[i];

                for (int j = i + 1; j < dotsCount; j++)
                {
                    if (dots[j].X == impossibleDot.X && dots[j].Y == impossibleDot.Y) continue;

                    // У прямой есть направляющий вектор (a, b) если по точкам, то 
                    // Если у двух прямых направляющие векторы совпадают (по направлению)
                    // то прямые паралельны, но в нашем случае они выходят из одной 
                    // точки (startLineDot) и поэтому обязаны совпасть,
                    // а значит третья точка лежит на одной прямой с первыми двумя
                    // так как нам важно только направление, то будем проверять условие
                    // a1 * b2 - b1 *a2 = 0

                    // Тута будем складывать точки лежащие на одной прямой с 
                    // i-ой и j-ой точками
                    Dot[] foundedDots = new Dot[dotsCount];
                    int foundedDotsCounter = 0;

                    float a1 = dots[j].X - startLineDot.X;
                    float b1 = dots[j].Y - startLineDot.Y;

                    for (int k = j + 1; k < dotsCount; k++)
                    {
                        if (dots[k].X == impossibleDot.X && dots[k].Y == impossibleDot.Y) continue;

                        float a2 = dots[k].X - startLineDot.X;
                        float b2 = dots[k].Y - startLineDot.Y;

                        if (a1 * b2 - b1 * a2 == 0)
                        {
                            // точка наша, добавляем ее в массив найденных
                            foundedDots[foundedDotsCounter] = dots[k];
                            foundedDotsCounter += 1;
                            // помечаем ее
                            dots[k] = impossibleDot;
                        }
                    }

                    // Если мы нашли хоть одну "третью" точку --- показываем массив точек
                    if (foundedDotsCounter > 0)
                    {
                        System.Console.Write("({0}, {1}), ", dots[i].X, dots[i].Y);
                        System.Console.Write("({0}, {1}), ", dots[j].X, dots[j].Y);

                        for (int l = 0; l < foundedDotsCounter; l++)
                        {
                            System.Console.Write("({0}, {1}), ", foundedDots[l].X, foundedDots[l].Y);
                        }
                        System.Console.WriteLine();
                    }
                }
            }
        }
    }

--------------------

design, simplicity, and experience with a technology focus

ivashkanet

Дата 12.10.2006, 15:18 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149

И еще: из за особенностей работы с числами с плавающей точкой (и не только) проверку на ноль лучше заменить на:

Код


System.Math.Abs( a1 * b2 - b1 * a2) < .0001

--------------------

design, simplicity, and experience with a technology focus

Ambition

Дата 12.10.2006, 16:17 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.10.2006

Репутация: нет
Всего: нет

спасибо

ivashkanet

Дата 12.10.2006, 17:33 (ссылка)

(нет голосов)

Загрузка ...

Кодю потиху

Профиль
Группа: Участник Клуба
Сообщений: 3684
Регистрация: 23.2.2006
Где: Гомель, Беларусь

Репутация: 9
Всего: 149

Цитата(Ambition @ 12.10.2006, 16:17

)

спасибо

Не за что

P.S. Ambition, пометь тему решенной.

--------------------

design, simplicity, and experience with a technology focus

Ambition

Дата 12.10.2006, 17:39 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 29
Регистрация: 10.10.2006

Репутация: нет
Всего: нет

сори, ок

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »