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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 31, средняя оценка - 4.65
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
#1

Определить координаты вершины треугольника - C++

12.12.2010, 14:36. Просмотров 3824. Ответов 34
Метки нет (Все метки)

Здравствуйте, снова обращаюсь к вам за помощью.
Прошу помочь в таком задании, искал вроде ничего похожего не нашел.

 Комментарий модератора 
Дублирование тем запрещено правилами форума (п. 3.4).
Не плодите одинаковых тем.
Миниатюры
Определить координаты вершины треугольника  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
12.12.2010, 14:36     Определить координаты вершины треугольника
Посмотрите здесь:

C++ Даны координаты вершин треугольника и координаты некоторой точки внутри него
Найти координаты четвертой вершины квадрата C++
C++ Определить координаты вершин прямоугольного треугольника
C++ Найти координаты 4 вершины
Определить, какие вершины достижимы из заданной вершины S C++
C++ Заданы координаты трех точек. Определить периметр треугольника, вершинами которого являются заданные точк
Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.12.2010, 19:06     Определить координаты вершины треугольника #21
Вышеприведенная программа от BrumbleHorse работает неверно, например при вводе
0, 1
1, 0
7, 5
Вот так будет правильнее:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
//////////////////////////////////////////////////////////////////////////////////////
//Для треугольника с целокоординатными вершинами по известным вершинам A(0, 0) и B 
//найти такую вершину C, чтобы площадь треугольника была минимально возможной.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
void  get_C_vertice(int  Bx, int  By, int& Cx, int&  Cy)
{
    Cx                   = 1;
    Cy                   = 0;
    double  y_delta_min  = 10;
 
    //Пробегаемся от точки A(0, 0) до точки B по отрезку AB в поисках точки, 
    //ближайшей к этой прямой:
    for(int x_cur = 0; x_cur != Bx; x_cur += Bx / abs(Bx))
    {
        double  y              = static_cast<double>(By) / Bx * x_cur;
        double  y_floor_delta  = abs(floor  (y) - y);
        double  y_ceil_delta   = abs(ceil   (y) - y);
 
        if(y_floor_delta == 0.0)           
        {
            if(y_delta_min > 1.0)
            {
                Cx           = x_cur;
                Cy           = static_cast<int>(y) + 1;                
                y_delta_min  = 1.0;            
            }            
        }   
        else if(std::min(y_floor_delta, y_ceil_delta) < y_delta_min)
        {
            Cx = x_cur;
            if(y_floor_delta < y_ceil_delta)
            {                
                Cy           = static_cast<int>(floor(y));
                y_delta_min  = y_floor_delta;                
            }
            else
            {                
                Cy           = static_cast<int>(ceil(y));
                y_delta_min  = y_ceil_delta;            
            }        
        }
    }
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale("")); 
    int Bx = 0;
    int By = 0;
 
    do
    {
        std::cout << std::endl
                  << "Введите координаты вершины B:"
                  << std::endl;
        
        std::cout << "Bx = ";
        std::cin >> Bx;
 
        
        std::cout << "By = ";
        std::cin >> By;    
    }while(   Bx == 0
           && By == 0);
 
    int Cx = 0;
    int Cy = 0;
 
    get_C_vertice(Bx, By, Cx, Cy);
    std::cout << "При заданных вершинах треугольника A(0, 0) и B("
              << Bx
              << ", "
              << By
              << ")"
              << std::endl
              << "треугольник будет иметь минимально возможную площадь "
              << std::endl
              << "при вершине в точке C("
              << Cx
              << ", "
              << Cy
              << ")."
              << std::endl;             
}
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
24.12.2010, 21:34     Определить координаты вершины треугольника #22
Цитата Сообщение от BrumbleHorse Посмотреть сообщение
одна из точек С, дающих минимальную площадь, всегда окажется на краю диапазона.. это происходит из-за того, что мы используем целочисленные координаты.. соответственно, если точка Б не лежит на прямой, проходящей через начало координат, то самая маленькая площадь всегда составит 0,5. И таких точек С,дающих площадь 0,5, найдется много в заданном диапазоне(т е чем больше координаты очередной подходящей точки С, тем более вытянутым будет треугольник, а площадь у него так и будет этой минимальной-0,5.. Если же Б лежит на прямой,проходящей через начало координат (т е Х и У у Б равны), то никакая точка С не даст нам этой минимальной площади 0,5 ( да и если разница между Х и У точки Б велика то тоже минимальная площадь будет больше)..в этом случае минимальная площадь будет варьироваться в зависимости от координат Б..
Не знаю, как Вы рассуждали, но это известная задача, и ее ответ Smin = 0.5*NOD(a,b), где NOD - наибольший общий делитель.

Добавлено через 25 минут
Цитата Сообщение от Mr.X Посмотреть сообщение
Вот так будет правильнее:
C++
1
2
3
4
void  get_C_vertice(int  Bx, int  By, int& Cx, int&  Cy)
{
    Cx                   = 1;
    Cy                   = 0;
Уже не верно - точка (1,0) будет следующей ближайшей только при Bx>=By.

И дальше у тебя цикл идет как y(x), но когда By>Bx надо бежать как x(y) - смотри алгоритм Брезенхейма, короче.
BrumbleHorse
120 / 120 / 11
Регистрация: 18.09.2010
Сообщений: 212
24.12.2010, 21:37     Определить координаты вершины треугольника #23
Цитата Сообщение от accept Посмотреть сообщение
не надо писать алгоритм для 0.5, если там может быть не 0.5
для всех случаев нужен один алгоритм
У меня там и есть один алгоритм.. постараюсь донести то, что я хотел сказать:
если взять любой треугольник, заданный целочисленными координатами, его площадь не может быть менее 0,5..
Цитата Сообщение от accept Посмотреть сообщение
в этой задаче точка B всегда лежит на прямой, проходящей через начало координат, потому что речь идёт о треугольнике ABC
Извиняюсь я не то имел ввиду.. я имел ввиду,что когда точка Б лежит на прямой у=х...
Цитата Сообщение от Mr.X Посмотреть сообщение
Вышеприведенная программа от BrumbleHorse работает неверно, например при вводе
0, 1
1, 0
7, 5
Действительно, когда вводится точка Б с одной из координат равной нулю,то моя программа работает неверно.. а вот по Б(7,5) у меня вопрос: ваша программа при Б(7,5) выдает точку С(0,1) и площадь соответственно будет 3,5.. но если взять например другую точку С (-25,-18), то с ней площадь составит 0,5, что меньше, чем 3,5..

Добавлено через 1 минуту
Цитата Сообщение от Напильнег Посмотреть сообщение
Не знаю, как Вы рассуждали, но это известная задача, и ее ответ Smin = 0.5*NOD(a,b), где NOD - наибольший общий делитель.
Никогда раньше не встречал такую задачу .. Спасибо буду знать..
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
24.12.2010, 22:46     Определить координаты вершины треугольника #24
Цитата Сообщение от BrumbleHorse Посмотреть сообщение
Действительно, когда вводится точка Б с одной из координат равной нулю,то моя программа работает неверно.
Только не надо по этому поводу ковыряться в алгоритме для нормального, "наклонного" отрезка AB, пытаясь сделать его универсальным - этот примитивный случай надо тупо выделять и выписывать примитивное решения для него особо (модуль ненулевой координаты пополам).

Цитата Сообщение от BrumbleHorse Посмотреть сообщение
а вот по Б(7,5) у меня вопрос: ваша программа при Б(7,5) выдает точку С(0,1) и площадь соответственно будет 3,5
Егойная программа у меня на (7,5) выдает (3,2), что правильно.
BrumbleHorse
120 / 120 / 11
Регистрация: 18.09.2010
Сообщений: 212
24.12.2010, 23:11     Определить координаты вершины треугольника #25
Да, его программа выдает 3,2 на 7,5 - скомпилировал ее компилятором Visual Studio.. до этого я ее скомпилировал GNU GCC, почему-то не было русского шрифта и выдавала на все ответ 0,1..
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
24.12.2010, 23:14     Определить координаты вершины треугольника #26
Цитата Сообщение от Напильнег Посмотреть сообщение

C++
1
2
3
4
void  get_C_vertice(int  Bx, int  By, int& Cx, int&  Cy)
{
    Cx                   = 1;
    Cy                   = 0;
Уже не верно - точка (1,0) будет следующей ближайшей только при Bx>=By.

И дальше у тебя цикл идет как y(x), но когда By>Bx надо бежать как x(y) - смотри алгоритм Брезенхейма, короче.
Значения
Cx = 1;
Cy = 0;
будут возвращены в случае, если цикл не выполнится ни разу, т.е. когда вершина B лежит на оси y. При выполнении хотя бы одной итерации цикла эти значения затираются. А вот по какой координате устраивать цикл, - это по-моему все равно, так как все отсекаемые от клеток треугольники подобны друг другу, и точка, ближайшая к прямой по x, будет к ней ближайшей и по y.
В общем, читайте внимательнее. Но если приведете пример неправильной работы моей программы, то буду признателен за конструктивную критику.
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
25.12.2010, 00:27  [ТС]     Определить координаты вершины треугольника #27
Что-то я совсем запутался. Какая из программ правильная ?
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
25.12.2010, 05:08     Определить координаты вершины треугольника #28
при любой точке B координаты точки C будут одними из:
С(0; 1) || С(1; 0) || С(-1; 0) || С(0; -1)
знак определяется по координатам точки B
а площадь берётся наименьшая из двух

бывает несколько точек C ещё, которые дают одинаковые площади

B(5; 0), C(0; 1)
B(5; 0), C(0; -1)
B(5; 0), C(1; 1)
B(5; 0), C(1; -1)
...

или
B(1; 0), C(0; 1)
B(1; 0), C(0; -1)
B(1; 0), C(1; 1)
B(1; 0), C(1; -1)
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
25.12.2010, 10:36     Определить координаты вершины треугольника #29
Цитата Сообщение от Stormfire Посмотреть сообщение
Что-то я совсем запутался. Какая из программ правильная ?
Ну, ежели для вас программа, для которой приведены примеры неправильной работы, может считаться правильной, то вы неизбежно запутаетесь.
А какие у вас сомнения относительно правильности моей программы, мне просто интересно?

Добавлено через 1 час 48 минут
Цитата Сообщение от accept Посмотреть сообщение
при любой точке B координаты точки C будут одними из:
С(0; 1) || С(1; 0) || С(-1; 0) || С(0; -1)
Эта тема какой-то чемпион по количеству ложных утверждений.
Если рассматривать вершины B и C как векторы, то площадь треугольника равна половине площади построенного на них параллелограмма, т.е.

S = 0.5 * abs(Bx*Cy – By*Cx),

т.е. задача состоит в поиске минимальной по модулю ненулевой линейной комбинации чисел Bx и By, которая, согласно известной теореме, равна по модулю НОД(Bx, By), а минимальная площадь треугольника, соответственно,

Smin = 0.5 * НОД(Bx, By),

как уже здесь писали выше.
Если числа Bx и By взаимно простые, то НОД(Bx, By) = 1, и Smin = 0.5 (один из выступавших посчитал, что это верно для всех случаев).
Если же Bx делит By, то НОД(Bx, By) = |Bx|, и площадь равна
Smin = 0.5 * |Bx|,
и в этом случае решением будет Cx = 0, Cy = 1.
Если же By делит Bx, то, соответственно, Cx = 1, Cy = 0,
т.е. вы приняли за общий случай другую крайность (только еще со знаками там заморочились, которые, на самом деле, ни на что не влияют).
Ну а истина лежит посередине, т.е. в моей программе.

Добавлено через 3 часа 22 минуты
Вот так покрасивше будет:

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
//////////////////////////////////////////////////////////////////////////////////////
//Для треугольника с целокоординатными вершинами по известным вершинам A(0, 0) и B 
//найти такую вершину C, чтобы площадь треугольника была минимально возможной.
//////////////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cmath>
#include <iostream>
//////////////////////////////////////////////////////////////////////////////////////
int  gcd(int A, int B)
{
    if(!B) return abs(A);    
    return  gcd(abs(B), abs(A) % abs(B));
}
//////////////////////////////////////////////////////////////////////////////////////
void  get_C_vertice(int  Bx, int  By, int&  Cx, int&  Cy)
{
    if(!Bx)
    {
        Cx = 1;
        Cy = 0;    
        return;
    }
 
    int  gcd_Bx_By = gcd(Bx, By);   
 
    for(Cx = 0; (By * Cx + gcd_Bx_By) % Bx; ++Cx);
    Cy = (By * Cx + gcd_Bx_By) / Bx;
}
//////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale("")); 
    int Bx = 0;
    int By = 0;
 
    do
    {
        std::cout << std::endl
                  << "Введите координаты вершины B:"
                  << std::endl;
        
        std::cout << "Bx = ";
        std::cin >> Bx;
 
        
        std::cout << "By = ";
        std::cin >> By;    
    }while(   Bx == 0
           && By == 0);
 
    int Cx = 0;
    int Cy = 0;
 
    get_C_vertice(Bx, By, Cx, Cy);
    std::cout << "При заданных вершинах треугольника A(0, 0) и B("
              << Bx
              << ", "
              << By
              << ")"
              << std::endl
              << "треугольник будет иметь минимально возможную площадь "
              << std::endl
              << "при вершине в точке C("
              << Cx
              << ", "
              << Cy
              << ")."
              << std::endl;             
}
Напильнег
480 / 120 / 10
Регистрация: 30.09.2010
Сообщений: 473
25.12.2010, 11:37     Определить координаты вершины треугольника #30
Цитата Сообщение от Mr.X Посмотреть сообщение
Значения
Cx = 1;
Cy = 0;
будут возвращены в случае, если цикл не выполнится ни разу, т.е. когда вершина B лежит на оси y. При выполнении хотя бы одной итерации цикла эти значения затираются. А вот по какой координате устраивать цикл, - это по-моему все равно...
Разобрался - я так поверхностно глянул, подумал, что ты апроксимацию отрезка делать будешь, а у тебя все гораздо вульгарнее, но эффективо. А такой инициализацией ты борешься с вертикальными линиями. На целые числа это переделать бы как нибудь...

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

Цитата Сообщение от Mr.X Посмотреть сообщение
так как все отсекаемые от клеток треугольники подобны друг другу, и точка, ближайшая к прямой по x, будет к ней ближайшей и по y.
Да, действительно так.

Добавлено через 1 минуту
Цитата Сообщение от Mr.X Посмотреть сообщение
Эта тема какой-то чемпион по количеству ложных утверждений.
Даже я лоханулся слегка
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
26.12.2010, 10:27     Определить координаты вершины треугольника #31

Не по теме:

стер тут кое-что про наибольший общий делитель
переклинило, что НОД(5; 7) = 35



Цитата Сообщение от Mr.X
т.е. вы приняли за общий случай другую крайность (только еще со знаками там заморочились, которые, на самом деле, ни на что не влияют).
Цитата Сообщение от Mr.X
и в этом случае решением будет Cx = 0, Cy = 1.
Если же By делит Bx, то, соответственно, Cx = 1, Cy = 0,
B(-5; -5) наименьшая площадь будет с точками C(-1; 0) и C(0; -1)
и не только с ними

Добавлено через 2 минуты
Код
[guest@localhost tests]$ ./t

Введите координаты вершины B:
Bx = -5
By = -5
При заданных вершинах треугольника A(0, 0) и B(-5, -5)
треугольник будет иметь минимально возможную площадь 
при вершине в точке C(0, 1).
[guest@localhost tests]$
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
26.12.2010, 20:55  [ТС]     Определить координаты вершины треугольника #32
Цитата Сообщение от Mr.X Посмотреть сообщение
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
   //Пробегаемся от точки A(0, 0) до точки B по отрезку AB в поисках точки, 
    //ближайшей к этой прямой:
    for(int x_cur = 0; x_cur != Bx; x_cur += Bx / abs(Bx))
    {
        double  y              = static_cast<double>(By) / Bx * x_cur;
        double  y_floor_delta  = abs(floor  (y) - y);
        double  y_ceil_delta   = abs(ceil   (y) - y);
 
        if(y_floor_delta == 0.0)           
        {
            if(y_delta_min > 1.0)
            {
                Cx           = x_cur;
                Cy           = static_cast<int>(y) + 1;                
                y_delta_min  = 1.0;            
            }            
        }   
        else if(std::min(y_floor_delta, y_ceil_delta) < y_delta_min)
        {
            Cx = x_cur;
            if(y_floor_delta < y_ceil_delta)
            {                
                Cy           = static_cast<int>(floor(y));
                y_delta_min  = y_floor_delta;                
            }
            else
            {                
                Cy           = static_cast<int>(ceil(y));
                y_delta_min  = y_ceil_delta;            
            }        
        }
    }
}
Очень прошу добавить комментарии по каждой строке в этой части кода.
Не очень понятно, что происходит
А тема забавная получилась, столько людей отписалось. Спасибо большое всем.
Mr.X
Эксперт С++
3039 / 1684 / 265
Регистрация: 03.05.2010
Сообщений: 3,867
27.12.2010, 01:59     Определить координаты вершины треугольника #33
Цитата Сообщение от Stormfire Посмотреть сообщение
Очень прошу добавить комментарии по каждой строке в этой части кода.
Не очень понятно, что происходит
А тема забавная получилась, столько людей отписалось. Спасибо большое всем.
А там же в сообщении #29 моя программа с более простым и понятным кодом.
Stormfire
0 / 0 / 0
Регистрация: 29.11.2010
Сообщений: 43
27.12.2010, 02:11  [ТС]     Определить координаты вершины треугольника #34
Более простой код видел и вроде понял, хотелось-б более сложный понять
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.12.2010, 04:38     Определить координаты вершины треугольника
Еще ссылки по теме:

C++ Определить координаты четвертой вершины прямоугольника
Вычислить координаты четвертой вершины прямоугольника C++
Найти координаты четвертой вершины прямоугольника C++
Вершины треугольника имеют координаты C++
Заданы координаты трех вершин прямоугольника, необходимо определить координаты четвертой вершины C++

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

Или воспользуйтесь поиском по форуму:
accept
4817 / 3237 / 165
Регистрация: 10.12.2008
Сообщений: 10,682
27.12.2010, 04:38     Определить координаты вершины треугольника #35
Цитата Сообщение от accept
при любой точке B координаты точки C будут одними из:
С(0; 1) || С(1; 0)
а площадь берётся наименьшая из двух
и вот пример

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
50
51
52
53
54
55
56
57
#include <stdio.h>
 
struct point {
    int x, y;
};
 
double func(struct point *c, const struct point *b);
 
int main(void)
{
    struct point b, c;
    double minarea;
    
    printf("input B(x, y): ");
    fflush(stdout);
    
    if (scanf("%d ,%d%*c", &b.x, &b.y) != 2) {
        fprintf(stderr, "error: input" "\n");
        return 1;
    }
    
    minarea = func(&c, &b);
    printf("minimal area = %.1f, C(%d; %d)" "\n", minarea, c.x, c.y);
    
    return 0;
}
 
double area_triangle(const struct point *a,
                     const struct point *b,
                     const struct point *c);
 
double func(struct point *c, const struct point *b)
{
    double s1, s2, area;
    struct point c1 = { 1, 0 }, c2 = { 0, 1 };
    struct point a = { 0, 0 };
    
    s1 = area_triangle(&a, b, &c1);
    s2 = area_triangle(&a, b, &c2);
    if (s1 >= s2 || s1 == 0.0)
        area = s2 , *c = c2;
    else
        area = s1 , *c = c1;
    return area; 
}
 
double area_triangle(const struct point *a,
                     const struct point *b,
                     const struct point *c)
{
    double ar = 0.5 * (
        a->x * b->y - a->y * b->x +
        b->x * c->y - b->y * c->x +
        c->x * a->y - c->y * a->x
    );
    return ar < 0 ? ar * -1.0 : ar;
}
Код
[guest@localhost tests]$ ./t
input B(x, y): -5,-6
minimal area = 2.5, C(0; 1)
[guest@localhost tests]$ ./t
input B(x, y): -6, -5
minimal area = 2.5, C(1; 0)
[guest@localhost tests]$

естественно там больше точек C и они не только еденицу могут содержать
например B(-5; -5), C(-3; -2)
Yandex
Объявления
27.12.2010, 04:38     Определить координаты вершины треугольника
Ответ Создать тему
Опции темы

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