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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
persalena
0 / 0 / 0
Регистрация: 02.12.2008
Сообщений: 23
#1

Помогите с алгоритмом - C++

09.09.2009, 19:19. Просмотров 639. Ответов 6
Метки нет (Все метки)

Даны координаты вершин двух трапеций. нужно проверить вложена ли одна трапеция в другую . Подскажите какую-нибудь идею, а то у меня выходит как-то слишком громоздко, некрасиво и вероятнее всего неправильно...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.09.2009, 19:19
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Помогите с алгоритмом (C++):

Помогите с алгоритмом - C++
F(a)+2F(a+h)+2F(a+2h)+...+2F(a+(N-1)h)+F(a+Nh). При F(x)=(x^2+1)(cosx*cosx)

помогите с алгоритмом! - C++
Заполните пустые ячейки пирамиды числами так, чтобы каждое число, которое содержится в прямоугольнике, равнялось сумме чисел, расположенных...

Помогите с алгоритмом - C++
Нужно написать программу сравнения 3 чисел. Без использования массивов, функций, управляющего else. то есть только используя if

Помогите с блок-схемой и алгоритмом - C++
Есть только листинг программы(((((((((( lines.cpp: #include "windows.h" #include "resource.h" #include "random.h" ...

польская инверсная запись. Помогите с алгоритмом. - C++
Не знаю как организовать алгоритм польской инверсной записи на С++. Если кто-то знает помогите пожалуйста.

Помогите плиз с алгоритмом проги (нужно отсортировать матрицу) - C++
Задача: Характеристикой столбца целочисленной матрицы назовём сумму модулей его отрицательных нечётных элементов. Переставляя столбцы...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
TanT
эволюционирую потихоньку
465 / 463 / 43
Регистрация: 30.06.2009
Сообщений: 1,399
09.09.2009, 20:30 #2
Что есть трапеция? С точки зрения меня - это область пространства, ограниченного отрезками прямых линий.
Каждая сторона трапеции, если её бесконечно продолжит, делит всю двумерную плоскоть пополам, и, оставшиеся две вершины, через которые не проходит воображаемая прямая, лежат по одну сторону этой самой прямой.
С точки зрения алгоритма кажется самым простым строить уравнение прямой y=kx+b для каждой пары точек одной из трапеций, находит в какой полуплоскости лежать оставшиеся две вершины и в какой полуплоскости лежать точки второй трапеции. Если точки второй трапеции лежат в разных полуплоскостях - уже точно не вписанных трапеции. Если по ходу проверки вершины второй трапеции лежат в одной и тойже полуплоскости что и оставшиеся вершины первой трапеции или всегда в противоположной. Тут ключевое слово "всегда". То соответственно можно вписать. иначе нет.
Вот как-то так.
P.S. можно конечно проверять где пересекаются уравнения прямых каждой из сторон обоих трапеций и проверять не попадаются эти точки в отрезках прямых, ограниченных вершинами трапеций. но это ИМХО сложнее.
АНК
124 / 115 / 2
Регистрация: 27.02.2007
Сообщений: 291
09.09.2009, 20:57 #3
Опишите свой алгоритм, посмотрим ...
M128K145
Эксперт С++
8286 / 3505 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
09.09.2009, 22:01 #4
Вот у нас есть такие данные
Помогите с алгоритмом
Тогда имеем
точка 1: если x1 > i1 и y1 < j1
точка 2: если x2 > i2 и y2 > j2
точка 3: если x3 < i3 и y3 > j3
точка 4: если x4 < i4 и y4 < j4
То трапеция А содержит трапецию B.
Вот небольшой
код
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
#include <iostream>
 
bool Content(int tr1[4][2], int tr2[4][2])
{
    return ((tr1[0][0] > tr2[0][0]) && (tr1[0][1] < tr2[0][1]) &&
        (tr1[1][0] > tr2[1][0]) && (tr1[1][1] > tr2[1][1]) &&
        (tr1[2][0] < tr2[2][0]) && (tr1[2][1] > tr2[2][1]) &&
        (tr1[3][0] < tr2[3][0]) && (tr1[3][1] < tr2[3][1])) ? true : false;
}
 
int main()
{
    setlocale(LC_ALL, "Russian");
    int trap1[4][2], trap2[4][2], i;
 
    std::cout<<"Введите координаты трапеции A:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<"Введите координаты точки A"<<i+1<<":\nx"<<i+1<<"> ", std::cin>>trap1[i][0];
        std::cout<<"y"<<i+1<<"> ", std::cin>>trap1[i][1];
    }
 
    std::cout<<"Введите координаты трапеции B:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<"Введите координаты точки B"<<i+1<<":\ni"<<i+1<<"> ", std::cin>>trap2[i][0];
        std::cout<<"j"<<i+1<<"> ", std::cin>>trap2[i][1];
    }
 
    if(Content(trap1, trap2))
        std::cout<<"Первая трапеция содержит вторую\n";
    else
        std::cout<<"Первая трапеция не содержит вторую\n";
    system("pause");
    return 0;
}
, который выполняет эту проверку.
Проверку на ввод некорректных данных не делал
АНК
124 / 115 / 2
Регистрация: 27.02.2007
Сообщений: 291
09.09.2009, 22:19 #5
Цитата Сообщение от M128K145 Посмотреть сообщение
Проверку на ввод некорректных данных не делал
А если сначала введены вершины маленькой трапеции, или с правой вершины начали, или обход вершин в разные сторона, да и вообще вершины не попорядку. Вот это-то и усложняет алгоритм на порядок.
M128K145
Эксперт С++
8286 / 3505 / 143
Регистрация: 03.07.2009
Сообщений: 10,706
09.09.2009, 23:53 #6
АНК, ну где-то так, чтобы точно не
запутаться
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
46
47
48
49
bool Content(int tr1[4][2], int tr2[4][2])
{
    return (((tr1[0][0] > tr2[0][0]) && (tr1[0][1] < tr2[0][1]) &&
        (tr1[1][0] > tr2[1][0]) && (tr1[1][1] > tr2[1][1]) &&
        (tr1[2][0] < tr2[2][0]) && (tr1[2][1] > tr2[2][1]) &&
        (tr1[3][0] < tr2[3][0]) && (tr1[3][1] < tr2[3][1])) ||
        ((tr2[0][0] > tr1[0][0]) && (tr2[0][1] < tr1[0][1]) &&
        (tr2[1][0] > tr1[1][0]) && (tr2[1][1] > tr1[1][1]) &&
        (tr2[2][0] < tr1[2][0]) && (tr2[2][1] > tr1[2][1]) &&
        (tr2[3][0] < tr1[3][0]) && (tr2[3][1] < tr1[3][1]))) ? true : false;
}
char* Top(int i) 
{
    char *top;
    switch(i)
    {
    case 0: top = "Введите координаты верхней левой вершины";break;
    case 1: top = "Введите координаты верхней правой вершины";break;
    case 3: top = "Введите координаты нижней правой вершины";break;
    default:top = "Введите координаты нижней левой вершины";
    }
    return top;
}
int main()
{
    setlocale(LC_ALL, "Russian");
    int trap1[4][2], trap2[4][2], i;
 
    std::cout<<"Введите координаты трапеции A:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<Top(i)<<":\nx"<<i+1<<"> ", std::cin>>trap1[i][0];
        std::cout<<"y"<<i+1<<"> ", std::cin>>trap1[i][1];
    }
 
    std::cout<<"Введите координаты трапеции B:\n";
    for(i = 0; i < 4; ++i)
    {
        std::cout<<Top(i)<<":\ni"<<"> ", std::cin>>trap2[i][0];
        std::cout<<"j"<<i+1<<"> ", std::cin>>trap2[i][1];
    }
 
    if(Content(trap1, trap2))
        std::cout<<"Первая трапеция содержит вторую\n";
    else
        std::cout<<"Первая трапеция не содержит вторую\n";
    system("pause");
    return 0;
}
да, понимаю что я не учел углы и все такое, но основную суть я думаю выложил
odip
Эксперт С++
7157 / 3297 / 59
Регистрация: 17.06.2009
Сообщений: 14,164
10.09.2009, 10:36 #7
M128K145 - твой алгоритм скорее всего неправильный.
Правильный алгоритм привел TanT в Помогите с алгоритмом
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.09.2009, 10:36
Привет! Вот еще темы с ответами:

Помогите плиз с алгоритмом проги (переставить слова в строке) - C++
Задача: В заданном тексте поменять местами каждые два соседних слова. Но нужно сделать, не используя библиотеки string. Допустим...

Помощь с алгоритмом - C++
Начал изучать массивы и тут задание : Найти среди элементов массива значение 2 Я в целом понимаю все это,но не знаю как выглядит алгоритм...

что не так с алгоритмом? - C++
пишу програму соответственно алгоритму вот код #include &lt;iostream.h&gt; #include &lt;conio.h&gt; #include &lt;string.h&gt; #include &lt;math.h&gt;...

Кодирование алгоритмом Хаффмана - C++
Проблема - такая : Есть рабочая программа, которая кодирует текстовый файл алгоритмом хаффмана. Кодирует она двоичным кодом. Присвоение...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.09.2009, 10:36
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru