Найти треугольник наибольшей площади с вершинами в данных точках

@Ирина 379 · Регистрация: 15.10.2014

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

Дано натуральное число n. С помощью двумерного действительного числового массива [xij]i=1,2; j=1,...,n на плоскости задано n точек так, что x1j, x2j – координаты j-й точки. Найти треугольник наибольшей площади с вершинами в этих точках.

Помогите пожалуйста дописать, не получается, заранее спасибо!

C++

#include <iostream>
#include <cmath>
 
using namespace std;
int main()
{
    int Ax,Ay,Bx,By,Cx,Cy,n;
    int mas[2][10];
    cout<<"n=";
    cin>>n;
    double S;
    for (int i=0;i<2;i++)
        for( int j=0;j<n;j++)
        cin>>mas[i][j];
    for (int i=0;i<2;i++)
        for( int j=0;j<n;j++)
        {
    mas[0][0]=mas[Ax][Ay];
    mas[0][1]=mas[Bx][By];
    mas[0][n-1]=mas[Cx][Cy];
        }
    S=0.5*abs((Ax-Cx)*(By-Cy)-(Bx-Cx)*(Ay-Cy));
    
    cout<<S;
system ("pause");
return 0;
}

@nmcf · 19.11.2014, 08:29

C++

int main()
{
    int Ax,Ay,Bx,By,Cx,Cy,n;
    int mas[10][2];
    cout<<"n=";
    cin>>n;
    double S, A, B, C, p;
 
    for (int i=0;i<n;i++) cin >> mas[i][0] >> mas[i][1]; // ввод пары x и y
 
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++)
            {
                // Вершины
                Ax = m[i][0]; // x
                Ay = m[i][1]; // y
                Bx = m[j][0];
                By = m[j][1];
                Cx = m[k][0];
                Cy = m[k][1];
                // Стороны
                A = sqrt((Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By));
                B = sqrt((Ax - Cx) * (Ax - Cx) + (Ay - Cy) * (Ay - Cy));
                C = sqrt((Bx - Cx) * (Bx - Cx) + (By - Cy) * (By - Cy));
                p = (A + B + C) / 2; // полупериметр
                S = sqrt(p * (p - A) * (p - B) * (p - C)); // площадь
            }
    
    cout << S;
 
    system ("pause");
    return 0;
}

@Ирина 379 · 19.11.2014, 19:31 **[ТС]**

cпасибо, Вам, огромное!!!!!

@Ирина 379 · 23.11.2014, 22:34 **[ТС]**

Написали код, но не понятно, что производится в цикле (там где i,j,k). И почему вершины задаются именно таким набором координат? Заранее спасибо!!!!
Условие задачи:
Дано натуральное число n. С помощью двумерного действительного числового массива [xij]i=1,2; j=1,...,n на плоскости задано n точек так, что x1j, x2j – координаты j-й точки. Найти треугольник наибольшей площади с вершинами в этих точках.

C++

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    int Ax,Ay,Bx,By,Cx,Cy,n;
    int m[10][2];
    cout<<"n=";
    cin>>n;
    double S, A, B, C, p;
 
    for (int i=0;i<n;i++) cin >> m[i][0] >> m[i][1]; // ввод пары x и y
 
    for (int i = 0; i < n - 2; i++)
        for (int j = i + 1; j < n - 1; j++)
            for (int k = j + 1; k < n; k++)
            {
                // Вершины
                Ax = m[i][0]; // x
                Ay = m[i][1]; // y
                Bx = m[j][0];
                By = m[j][1];
                Cx = m[k][0];
                Cy = m[k][1];
                // Стороны
                A = sqrt(double((Ax - Bx) * (Ax - Bx) + (Ay - By) * (Ay - By)));
                B = sqrt(double((Ax - Cx) * (Ax - Cx) + (Ay - Cy) * (Ay - Cy)));
                C = sqrt(double((Bx - Cx) * (Bx - Cx) + (By - Cy) * (By - Cy)));
                p = (A + B + C) / 2; // полупериметр
                S = sqrt(p * (p - A) * (p - B) * (p - C)); // площадь
            }
    
    cout << S;
 
    system ("pause");
    return 0;
}

@TheCalligrapher · 24.11.2014, 04:08

Сообщение от Ирина 379

не понятно, что производится в цикле (там где i,j,k)

Циклы проходят по все возможным треугольникам, построенным на заданных точках.

В цикле производится вычисление площади каждого треугольника по формуле Герона. Однако программа не дописана: с вычисленной площадью ничего не делается. Т.е. она не проверяется на максимальность, как того требует условие задачи.

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

Сообщение от Ирина 379

почему вершины задаются именно таким набором координат

Не понял вопроса. Каким "именно таким"? Вершины задаются набором координат, прочитанным из входного потока.

@nmcf · 24.11.2014, 08:39

Да, забыл про максимум. Там пару строчек добавить. Допили.

@Ирина 379 · 25.11.2014, 00:39 **[ТС]**

Спасибо большое. Дописала, получилось

@Ирина 379 0 / 0 / 1 Регистрация: 15.10.2014 Сообщений: 29
	19.11.2014, 19:31 [ТС]	3
	cпасибо, Вам, огромное!!!!! 0

@TheCalligrapher Вездепух 11088 / 6055 / 1652 Регистрация: 18.10.2014 Сообщений: 15,200
	24.11.2014, 04:08	5
	Сообщение от Ирина 379 не понятно, что производится в цикле (там где i,j,k) Циклы проходят по все возможным треугольникам, построенным на заданных точках. В цикле производится вычисление площади каждого треугольника по формуле Герона. Однако программа не дописана: с вычисленной площадью ничего не делается. Т.е. она не проверяется на максимальность, как того требует условие задачи. Программа просто выводит самую последнюю вычисленную площадь, которая в общем случае не будет максимальной. Сообщение от Ирина 379 почему вершины задаются именно таким набором координат Не понял вопроса. Каким "именно таким"? Вершины задаются набором координат, прочитанным из входного потока. 1

@nmcf 7538 / 6399 / 2918 Регистрация: 14.04.2014 Сообщений: 27,865
	24.11.2014, 08:39	6
	Да, забыл про максимум. Там пару строчек добавить. Допили. 1

@Ирина 379 0 / 0 / 1 Регистрация: 15.10.2014 Сообщений: 29
	25.11.2014, 00:39 [ТС]	7
	Спасибо большое. Дописала, получилось 0

Опции темы