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

@Stormfire · Регистрация: 29.11.2010

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

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

Комментарий модератора

Дублирование тем запрещено правилами форума (п. 3.4).
Не плодите одинаковых тем.

@Mr.X · 24.12.2010, 19:06

Вышеприведенная программа от BrumbleHorse работает неверно, например при вводе
0, 1
1, 0
7, 5
Вот так будет правильнее:

C++

//////////////////////////////////////////////////////////////////////////////////////
//Для треугольника с целокоординатными вершинами по известным вершинам 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;             
}

@Напильнег · 24.12.2010, 21:34

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

одна из точек С, дающих минимальную площадь, всегда окажется на краю диапазона.. это происходит из-за того, что мы используем целочисленные координаты.. соответственно, если точка Б не лежит на прямой, проходящей через начало координат, то самая маленькая площадь всегда составит 0,5. И таких точек С,дающих площадь 0,5, найдется много в заданном диапазоне(т е чем больше координаты очередной подходящей точки С, тем более вытянутым будет треугольник, а площадь у него так и будет этой минимальной-0,5.. Если же Б лежит на прямой,проходящей через начало координат (т е Х и У у Б равны), то никакая точка С не даст нам этой минимальной площади 0,5 ( да и если разница между Х и У точки Б велика то тоже минимальная площадь будет больше)..в этом случае минимальная площадь будет варьироваться в зависимости от координат Б..

Не знаю, как Вы рассуждали, но это известная задача, и ее ответ Smin = 0.5*NOD(a,b), где NOD - наибольший общий делитель.

Добавлено через 25 минут

Сообщение от Mr.X

Вот так будет правильнее:

C++

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 · 24.12.2010, 21:37

Сообщение от 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 - наибольший общий делитель.

Никогда раньше не встречал такую задачу

.. Спасибо буду знать..

@Напильнег · 24.12.2010, 22:46

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

Действительно, когда вводится точка Б с одной из координат равной нулю,то моя программа работает неверно.

Только не надо по этому поводу ковыряться в алгоритме для нормального, "наклонного" отрезка AB, пытаясь сделать его универсальным - этот примитивный случай надо тупо выделять и выписывать примитивное решения для него особо (модуль ненулевой координаты пополам).

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

а вот по Б(7,5) у меня вопрос: ваша программа при Б(7,5) выдает точку С(0,1) и площадь соответственно будет 3,5

Егойная программа у меня на (7,5) выдает (3,2), что правильно.

@BrumbleHorse · 24.12.2010, 23:11

Да, его программа выдает 3,2 на 7,5 - скомпилировал ее компилятором Visual Studio.. до этого я ее скомпилировал GNU GCC, почему-то не было русского шрифта и выдавала на все ответ 0,1..

@Mr.X · 24.12.2010, 23:14

Сообщение от Напильнег

C++

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 · 25.12.2010, 00:27 **[ТС]**

Что-то я совсем запутался. Какая из программ правильная ?

accept · 25.12.2010, 05:08

при любой точке 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 · 25.12.2010, 10:36

Сообщение от 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++

//////////////////////////////////////////////////////////////////////////////////////
//Для треугольника с целокоординатными вершинами по известным вершинам 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;             
}

@Напильнег · 25.12.2010, 11:37

Сообщение от Mr.X

Значения
Cx = 1;
Cy = 0;
будут возвращены в случае, если цикл не выполнится ни разу, т.е. когда вершина B лежит на оси y. При выполнении хотя бы одной итерации цикла эти значения затираются. А вот по какой координате устраивать цикл, - это по-моему все равно...

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

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

Сообщение от Mr.X

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

Да, действительно так.

Добавлено через 1 минуту

Сообщение от Mr.X

Эта тема какой-то чемпион по количеству ложных утверждений.

Даже я лоханулся слегка

accept · 26.12.2010, 10:27

Не по теме:

стер тут кое-что про наибольший общий делитель
переклинило, что НОД(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 · 26.12.2010, 20:55 **[ТС]**

Сообщение от Mr.X

C++

   //Пробегаемся от точки 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 · 27.12.2010, 01:59

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

Очень прошу добавить комментарии по каждой строке в этой части кода.
Не очень понятно, что происходит

А тема забавная получилась, столько людей отписалось. Спасибо большое всем.

А там же в сообщении #29 моя программа с более простым и понятным кодом.

@Stormfire · 27.12.2010, 02:11 **[ТС]**

Более простой код видел и вроде понял, хотелось-б более сложный понять

accept · 27.12.2010, 04:38

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

при любой точке B координаты точки C будут одними из:
С(0; 1) || С(1; 0)
а площадь берётся наименьшая из двух

и вот пример

C

#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)

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	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) 0

@Напильнег 481 / 119 / 17 Регистрация: 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 Эта тема какой-то чемпион по количеству ложных утверждений. Даже я лоханулся слегка 0

accept 4866 / 3288 / 468 Регистрация: 10.12.2008 Сообщений: 10,570
	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]$ 0

@Mr.X 3225 / 1752 / 436 Регистрация: 03.05.2010 Сообщений: 3,867
	27.12.2010, 01:59	33
	Сообщение от Stormfire Очень прошу добавить комментарии по каждой строке в этой части кода. Не очень понятно, что происходит А тема забавная получилась, столько людей отписалось. Спасибо большое всем. А там же в сообщении #29 моя программа с более простым и понятным кодом. 0

@BrumbleHorse 122 / 122 / 16 Регистрация: 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 - наибольший общий делитель. Никогда раньше не встречал такую задачу .. Спасибо буду знать.. 0

@Напильнег 481 / 119 / 17 Регистрация: 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), что правильно. 1

@BrumbleHorse 122 / 122 / 16 Регистрация: 18.09.2010 Сообщений: 212
	24.12.2010, 23:11	25
	Да, его программа выдает 3,2 на 7,5 - скомпилировал ее компилятором Visual Studio.. до этого я ее скомпилировал GNU GCC, почему-то не было русского шрифта и выдавала на все ответ 0,1.. 0

@Stormfire 0 / 0 / 0 Регистрация: 29.11.2010 Сообщений: 43
	25.12.2010, 00:27 [ТС]	27
	Что-то я совсем запутался. Какая из программ правильная ? 0

@Stormfire 0 / 0 / 0 Регистрация: 29.11.2010 Сообщений: 43
	27.12.2010, 02:11 [ТС]	34
	Более простой код видел и вроде понял, хотелось-б более сложный понять 0