Форум программистов, компьютерный форум CyberForum.ru

Квадрат наибольшего периметра - C++

Восстановить пароль Регистрация
 
Nomad 94
1 / 1 / 0
Регистрация: 02.04.2012
Сообщений: 46
11.03.2013, 08:45     Квадрат наибольшего периметра #1
Вот эту задачу не могу реализовать.
Задано множество (n) точек на плоскости, Выбрать из них 4 разные точки, которые являются вершинами квадрата наибольшего периметра.Координаты каждой из точек вводятся с клавиатуры.

Добавлено через 12 минут
Задача для С++.

Добавлено через 39 минут
Алгоритм по-моему очевиден:
1)Задается функция определения расстояния между двумя точками, Определяется кол-во точек с одинаковыми расстояниями.
2)Определяется Перпендикулярность одинаковых прямых.(Определение кол-ва квадратов, и есть ли они вообще.)
3)Вычисляется периметр всех найденых квадратов, и определяется наибольший.
4)Вывод вершин квадрата наибольшего периметра.
Вот, но реализовать сам Я пока такой алгоритм средствами с++ не могу.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.03.2013, 08:45     Квадрат наибольшего периметра
Посмотрите здесь:

C++ Выбрать 3 разные точки заданного на плоскости множества точек,составляющие треугольник наибольшего периметра
C++ Квадрат наибольшего периметра
C++ Выбрать три разные точки заданного на плоскости множества точек, составляющие треугольник наибольшего периметра
C++ Из заданного на плоскости множества точек выбрать такие три, которые составляют треугольник наибольшего периметра.
C++ Найти квадрат наибольшего периметра
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.03.2013, 10:04     Квадрат наибольшего периметра #2
Цитата Сообщение от Nomad 94 Посмотреть сообщение
Алгоритм по-моему очевиден:
Значит полдела уже сделано. Начинайте писать код, что не ясно будет - спрашивайте.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.03.2013, 15:56     Квадрат наибольшего периметра #3
А как определять квадратность?
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
bool Check(Tpoint p, Tpoint p2, Tpoint p3, Tpoint p4)
{
 double d12;
 double d13;
 double d14;
 double d23;
 double d24;
 double d34;
 d12=sqrt((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)+(p1.z-p2.z)*(p1.z-p2.z));
 d13=sqrt((p1.x-p3.x)*(p1.x-p3.x)+(p1.y-p3.y)*(p1.y-p3.y)+(p1.z-p3.z)*(p1.z-p3.z));
 d14=sqrt((p1.x-p4.x)*(p1.x-p4.x)+(p1.y-p4.y)*(p1.y-p4.y)+(p1.z-p4.z)*(p1.z-p4.z));
 d23=sqrt((p2.x-p3.x)*(p2.x-p3.x)+(p2.y-p3.y)*(p2.y-p3.y)+(p2.z-p3.z)*(p2.z-p3.z));
 d34=sqrt((p3.x-p4.x)*(p3.x-p4.x)+(p3.y-p4.y)*(p3.y-p4.y)+(p3.z-p4.z)*(p3.z-p4.z));
 if ((d12!=d23)||(d12!=d23)||(d12!=d34)||(d12!=d14)||(d13!=d24)||(d13!=sqrt(2*d12)))
 {
  return false;
 }
 return true;
}
будет часто выдавать false из-за ошибок округления.

Добавлено через 1 минуту
Цитата Сообщение от Nomad 94 Посмотреть сообщение
Определяется Перпендикулярность одинаковых прямых.(Определение кол-ва квадратов, и есть ли они вообще.)
Зачем? Диагонали делят квадрат на теругольники, а треугольник - жёсткая фигура, то есть длины сторон однозначно определяют углы, но не наоборот, так что одна лишь перпендикулярность ещё не означает квадратности.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.03.2013, 16:18     Квадрат наибольшего периметра #4
Цитата Сообщение от taras atavin Посмотреть сообщение
А как определять квадратность?
Что если сравнивать разницу координат (по сути проекцию на ось)? Не будет никаких double'ов, если координаты целые.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
11.03.2013, 17:11     Квадрат наибольшего периметра #5
Цитата Сообщение от Tulosba Посмотреть сообщение
Не будет никаких double'ов, если координаты целые.
Допустим. (5, 1, 0), (8, 5 0), (4, 8, 0), (1, 4, 0) и (5, 1, 0), (6, 2, 0), (5, 3, 0), (4, 2, 0) - квадраты, а (5, 1, 0), (7, 5, 0), (3, 7, 0), (1, 3, 0), но во втором случае длины сторон не целые, координаты целые.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.03.2013, 17:21     Квадрат наибольшего периметра #6
Цитата Сообщение от taras atavin Посмотреть сообщение
но во втором случае длины сторон не целые, координаты целые.
А кто говорил про длины сторон?
Например для двух точек (т.е. для одной потенциальной стороны квадрата): (x1, y1) и (x2, y2) проекции будут |x1-x2|, |y1-y2|.
У противоположных сторон квадрата проекции должны быть одинаковые, независимо от того как квадрат наклонен на плоскости.
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.03.2013, 18:49     Квадрат наибольшего периметра #7
Для n точек количество возможных размещений в четырехугольники составит n! / (n - 4)!
Для 20 точек -- 116280 вариантов.
Для 100 точек -- 94109400 вариантов.

Оптимизируем:
Берем точку, и строим линию с каждой следующей точкой во множестве точек.
Проверяем наличие четырех других точек, дополняющих линию до двух квадратов, расположенных симметрично этой линии.
Если ни один из двух квадратов не существует, эта точка убирается из множества.Переходим к следующей точке.

Алгоритм простой. Нужно знание тригонометрии. Как найти координаты четырех возможных точек двух возможных кдватратов, если имеются только две точки одной стороны?
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.03.2013, 20:41     Квадрат наибольшего периметра #8
Цитата Сообщение от lemegeton Посмотреть сообщение
Для n точек количество возможных размещений в четырехугольники составит n! / (n - 4)!
Для 20 точек -- 116280 вариантов.
Для 100 точек -- 94109400 вариантов.
Что-то для 4 точек по Вашей формуле получается 4! = 24. Откуда?
St-Voland
171 / 79 / 3
Регистрация: 05.12.2012
Сообщений: 217
11.03.2013, 21:01     Квадрат наибольшего периметра #9
Цитата Сообщение от Tulosba Посмотреть сообщение
(x1, y1) и (x2, y2) проекции будут |x1-x2|, |y1-y2|.
У противоположных сторон квадрата проекции должны быть одинаковые, независимо от того как квадрат наклонен на плоскости
Да, однако это не критерий. Например, фигура (0,0), (1,2), (3,1) и (2,-1) - квадрат, с проекциями все гут. Если мы переместим вершину (3,1) в (1,1) условия |x1-x2|, |y1-y2| будут удовлетворяться - но это не квадрат. Да и на ромбе все крашится.

Цитата Сообщение от lemegeton Посмотреть сообщение
количество возможных размещений
Сочетания вполне справятся

В виду фразы ТС: "ввод данных с клавиатуры", хочется верить в маленькие значения n
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.03.2013, 21:30     Квадрат наибольшего периметра #10
Цитата Сообщение от St-Voland Посмотреть сообщение
Сочетания вполне справятся
Сочетания не справятся. Вернее, справятся, но перебирать все четыре точки в разных порядках придется.
Если abcd квадрат, то acbd совсем не квадрат.
Tulosba
:)
Эксперт С++
4378 / 3221 / 297
Регистрация: 19.02.2013
Сообщений: 9,044
11.03.2013, 22:05     Квадрат наибольшего периметра #11
Цитата Сообщение от St-Voland Посмотреть сообщение
Да, однако это не критерий. Например, фигура (0,0), (1,2), (3,1) и (2,-1) - квадрат, с проекциями все гут. Если мы переместим вершину (3,1) в (1,1) условия |x1-x2|, |y1-y2| будут удовлетворяться - но это не квадрат.
Если переместим (3,1) в (1,1), то для противоположных сторон проекции равны не будут.
Цитата Сообщение от St-Voland Посмотреть сообщение
Да и на ромбе все крашится.
Здесь согласен. Но я и не говорил, что условие достаточное

Добавлено через 16 минут
А что если проверить сумму проекций смежных сторон на разные оси координат?
Например, если нужно проверить на "квадратность" четырехугольник abcd нужно чтобы выполнялось равенство:
ax + bx = by + cy = cx + dx = dy + ay
s1lver
20 / 17 / 5
Регистрация: 25.01.2012
Сообщений: 66
11.03.2013, 22:41     Квадрат наибольшего периметра #12
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
42
43
44
45
#include <iostream>
#include <cmath>
#include <conio.h>
 
using namespace std;
 
class Point {
    public:
        int x,y;
};
 
double len(int x1, int y1, int x2 ,int y2);
 
int main()
{
    int n,a,b,c,d;
    cout << "Введите n: ";
    cin >> n;
    Point A[n];
    double max_p = 0;  //Максимальный периметр
    
    for (int i=0; i<n; i++) cin >> A[i].x >> A[i].y;
    
    //Пробегаем 4-ным циклом по массиву. Каждый счётчик цикла представляем в виде точки, таким образом перебираем все возможные варианты
    for (int i=0; i<n; i++) 
        for (int j=0; j<n; j++)
            for (int k=0; k<n; k++)
                for (int l=0; l<n; l++) {
                    a = len(A[i].x, A[i].y, A[j].x, A[j].y);
                    b = len(A[i].x, A[i].y, A[k].x, A[k].y);
                    c = len(A[j].x, A[j].y, A[l].x, A[l].y);
                    d = len(A[k].x, A[k].y, A[l].x, A[l].y);
                    if (a==b && a==c && a==d && (a*4>max_p)) max_p = 4*a;
                }
                
    cout << "Максимальный периметр: " << max_p;
    
    getch();
    return 0;
}
 
//Вычисление длины отрезка.
double len(int x1, int y1, int x2 ,int y2) {
    return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.03.2013, 22:47     Квадрат наибольшего периметра
Еще ссылки по теме:

C++ отношение наибольшего числа к наименьшему, квадрат суммы двух меньших по значению чисел
C++ Задача на структуры: выбор точек, образующих треугольник наибольшего периметра
Треугольник наибольшего периметра C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
lemegeton
 Аватар для lemegeton
2910 / 1339 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
11.03.2013, 22:47     Квадрат наибольшего периметра #13
Варианты с ромбами можно отсечь, сравнив длины диагоналей. У квадрата длины диагоналей должны совпасть.
Yandex
Объявления
11.03.2013, 22:47     Квадрат наибольшего периметра
Ответ Создать тему
Опции темы

Текущее время: 11:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru