Помогите решить исправить задачу

Question

помогите сделать задачу Дано N точек на плоскости. Найти: все наборы точек, принадлежащих одной прямой Написал ввод точек и сдвиг всех точек в одну четверть Не знаю как сделать, так чтобы прямые проходили через точки и выводил эти точки, и кол-во таких прямых

        #include <iostream>
    #include <math.h>
    #include <iomanip>
    #include <fstream>
    #include <Windows.h>

using namespace std;

void setOptions(void);

int main()
{
    setlocale(LC_ALL, "Rus");
    int N,variable,Z,amount;
    float straight_x=0,straight_y=0;
    float *Arr_x,*Arr_y,x,y,max_x,max_y;
    amount=1;

    variable=0;
    cout << "Введите кол-во точек N \n";
    cin >> N;
    Arr_x=new float[N];
    Arr_y=new float[N];
    
    for(variable=0;variable<N;variable++)
    {
        
    }


    for(variable=0;variable<N;variable++)
    {
        cout << "Точка "<< amount << endl;
        cout << "Введите координату x \n";
        cin >> x;
        Arr_x[variable]=x;
        cout << "Введите координату y \n";
        cin >> y;
        Arr_y[variable]=y;
        amount++;
    }

    amount=1;
    for(variable=0;variable<N;variable++)
    {
        if(Arr_x[variable]<0)
        {
            Arr_x[variable]=abs(Arr_x[variable]);
            if(Arr_x[variable]>straight_x)
            {
                straight_x=Arr_x[variable];
            }
        }
        if(Arr_y[variable]<0)
        {
            Arr_y[variable]=abs(Arr_y[variable]);
            if(Arr_y[variable]>straight_y)
            {
                straight_y=Arr_y[variable];
            }
        }

    }
    for(variable=0;variable<N;variable++)
    {
        Arr_x[variable]=Arr_x[variable]+straight_x;
        Arr_y[variable]=Arr_y[variable]+straight_y;
    }

Answer 1

Могу предложить алгоритм.

Две любые точки всегда задают прямую. Уравнение этой прямой можно получить по формуле.

f(x, y) = (y1 - y2)x + (x2 - x1)y + (x1y2 - x2y1) = 0

Далее все остальные точки прогоняем через формулу. Если значение равно 0 с заданной точность ε — т.е.

abs( f(xi, yi) ) <= ε

То значит точка лежит на прямой.

Значит берем и перебираем все возможные комбинации точек. Остается лишь отсеять повторяющиеся наборы точек.

Реализация:

#include <iostream>
#include <vector>
#include <algorithm>

struct Point {
    float x;
    float y;
    
    Point(float x, float y)
    : x(x), y(y)
    {}
};

const double epsilon = 1e-5;

std::vector<std::vector<size_t>> execute (std::vector<Point> & points)
{
    std::vector<std::vector<size_t>> answer;
    
    for (size_t i = 0; i < points.size(); i++)
    {
        for (size_t j = i + 1; j < points.size(); j++)
        {
            Point & p1 = points.at(i),
                  & p2 = points.at(j);
                  
            //Вычисляем коэффициенты для функции очередной прямой 
            float a = p1.y - p2.y,
                  b = p2.x - p1.x,
                  c = p1.x * p2.y - p2.x * p1.y;
                  
            std::vector<size_t> tanswer {i, j};
            
            for (size_t k = 0; k < points.size(); k++)
            { 
                if (k == i || k == j) continue;
                
                Point & current = points.at(k);
                float f = a * current.x + b * current.y + c; 
                
                //Проверяем на равенство нулю с точностью epsilon.
                if (std::abs(f) < epsilon)
                    tanswer.push_back(k);
            }
            //Сортируем промежуточный ответ 
            std::sort(tanswer.begin(), tanswer.end());
            
            //Проверяем, есть ли уже такая комбинация точек в ответе, если нет — добавляем 
            if (std::find(answer.begin(), answer.end(), tanswer) == answer.end())
                answer.push_back(tanswer);
        }
    }
    
    return answer;
}

int main() 
{
    std::vector<Point> p { Point(0, 1), Point(1, 1), Point(2, 1), Point(1, 0) , Point(22, 11), Point(11, 5.5)};
    auto answ = execute(p);
    
    for (auto c : answ)
    {
        for (auto i : c)
            std::cout << "{" << p.at(i).x << "," << p.at(i).y << "}, ";
        std::cout << std::endl;
    }
    
    return 0;
}

P.s. Для большего упрощения кода можно использовать специальные структуры данных, например Set для ответа.

Answer 2

По каждой паре неравных точек строите уравнение прямой ax + by + c = 0. Прямая должна проходить через обе точки. Если a < 0 or (a = 0 && b < 0) то меняем знаки всем коэффициентам в уравнении. Вместе с прямой сохраняем пару индексов точек, которые её задали. В худшем случае получим n(n-1)/2 прямых.

Зададим порядок на прямых:

l1 (a1x + b1y + c1 = 0) < l2 (a2x + b2y + c2 = 0) тогда и только тогда когда

a1b2 - a2b1 < 0 || (a1b2 - a2b1 = 0 && c1^2 (a2^2 + b2^2) < c2^2 (a1^2 + b1^2)).

Аналогично задаётся равенство:

l1 = l2 тогда и только тогда когда

a1b2 - a2b1 = 0 && c1^2 (a2^2 + b2^2) = c2^2 (a1^2 + b1^2).

Пользуясь неравенством сортируете прямые. После сортировки равные прямые оказываются в массиве рядом.

Пробегаете по массиву и, если соседние прямые равны, собираете индексы точек в группу. Все такие группы печатаете.

Сразу предупреждаю - это сложно. На Python это 48 строк очень непонятного кода. На C++ будет за полторы сотни.

БЛОГ НА HUSL

Помогите решить исправить задачу

Ответы (2 шт):