IPB
ЛогинПароль:

> Внимание!

1. Пользуйтесь тегами кода. - [code] ... [/code]
2. Точно указывайте язык, название и версию компилятора (интерпретатора).
3. Название темы должно быть информативным.
В описании темы указываем язык!!!

Наладить общение поможет, если вы подпишитесь по почте на новые темы в этом форуме.

 
 Ответить  Открыть новую тему 
> Геометрическая задача на С++, Нахождение треугольника минимальной площади
сообщение
Сообщение #1


Пионер
**

Группа: Пользователи
Сообщений: 51
Пол: Мужской
Реальное имя: Владимир

Репутация: -  0  +


Задача такая: Из заданного на плоскости множества точек выбрать 3, не лежащих на одной прямой и состовляющих треугольник наименьшей площади.
Как я понимаю плоскость задаем в виде двумерного массива?А что с этим массивом потом делать?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #2


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Плоскость нет (по-моему) смысла задавать двумерным массивом. Задавать нужно *точки*, а не плоскость. Точки можно задать (одномерным) массивом, каждый элемент - пара (x, y). Или двумя массивами - x[1..n] и y[1..n].

Лобовое решение - тремя вложенными циклами перебрать первую, вторую и третью точки, и выбрать наилучший треугольник. Это будет O(n^3).

Решение похитрее - за O(n^2). Расскажу, если кому-то действительно интересно.

Может можно и за O(n log n). Но это уже совсем сложно, надо думать.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #3


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


если границы цикла грамотно установить - оценка чуть получше будет... то есть каждое сочетание проверить один раз. Ведь треугольники из точек с номерами 1,2 и 3 (123, 132, 213, 231, 321, 312) имеют одну и ту же площадь.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Это не меняет асимптотики.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #5


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


я не спорю.
просто дополнила.


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #6


Пионер
**

Группа: Пользователи
Сообщений: 51
Пол: Мужской
Реальное имя: Владимир

Репутация: -  0  +


Вот что смог написать, только ничего не работает smile.gif

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{ clrscr();
int X[10],Y[10],i,j,k;
float s,Smin,a,b,c,p;
for (i=0;i<=9;i++)
{
X[i]=random(100);
Y[i]=random(100);
}

for (i=0;i<=9;i++)
{
a=abs(X[i]-Y[i]);
for (j=1;j<=9;j++)
{
b=abs(X[j]-Y[j]);

for (k=2;k<=9;k++)
{
c=abs(X[k]-Y[k]);
p=(a+b+c)/2;
s=sqrt(p*(p-a)*(p-b)*(p-c));
if (i==0) Smin=s;
else if (s<Smin) Smin=s;
}
}
}
cout<<"Smin="<<Smin;
getch();
return 0;
}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #7


просто человек
******

Группа: Пользователи
Сообщений: 3 641
Пол: Женский
Реальное имя: Юлия

Репутация: -  55  +


так... площадь ты пытаешься считать по формуле Герона - логично.
только а,b и c как-то странно находишь smile.gif
длина стороны - это расстояние между двумя точками, а не разность между двумя координатами одной точки...


--------------------
Все содержимое данного сообщения (кроме цитат) является моим личным скромным мнением и на статус истины в высшей инстанции не претендует.
На вопросы по программированию, физике, математике и т.д. в аське и личке не отвечаю. Даже "один-единственный раз" в виде исключения!
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #8


Пионер
**

Группа: Пользователи
Сообщений: 51
Пол: Мужской
Реальное имя: Владимир

Репутация: -  0  +


Ой!!Точно!Я чего то ступил))
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #9


Пионер
**

Группа: Пользователи
Сообщений: 51
Пол: Мужской
Реальное имя: Владимир

Репутация: -  0  +


А формула для длины отрезка такая sqrt[ (x1-x2)^2 + (y1-y2)^2 ]?Я переделал но все равно ничего не работает smile.gif

#include <stdio.h>
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
int main(void)
{ clrscr();
int X[10],Y[10],i,j,k;
float s,Smin,a,b,c,p;
for (i=0;i<=9;i++)
{
X[i]=random(100);
Y[i]=random(100);
}

for (i=0;i<=9;i++)
{
a=sqrt((X[i+1]-X[i])*(X[i+1]-X[i])+(Y[i+1]-Y[i])*(Y[i+1]-Y[i]);
for (j=1;j<=9;j++)
{
b=sqrt((X[j+1]-X[j])*(X[j+1]-X[j])+(Y[j+1]-Y[j])*(Y[j+1]-Y[j]);

for (k=2;k<=9;k++)
{
c=sqrt((X[k+1]-X[k])*(X[k+1]-X[k])+(Y[k+1]-Y[k])*(Y[k+1]-Y[k]);
p=(a+b+c)/2;
s=sqrt(p*(p-a)*(p-b)*(p-c));
if (i==0) Smin=s;
else if (s<Smin) Smin=s;
}
}
}
cout<<"Smin="<<Smin;
getch();
return 0;
}
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #10


Гость






попробуй вот так:
#include <conio.h>
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <values.h>

#define SQR(x) (x)*(x)

int main(void) {

clrscr();
int X[10],Y[10],i,j,k, min_1, min_2, min_3;
float Smin = MAXINT,a,b,c,p;
for (i=0;i<=9;i++) {
X[i]=random(100);
Y[i]=random(100);
cout << "(" << X[i] << ";" << Y[i] << ") ";
}

for (i=0;i<=9;i++) {
for (j=1;j<=9;j++) {

b=sqrt(SQR(X[j] - X[i]) + SQR(Y[j] - Y[i]));

for (k=2;k<=9;k++) {

c=sqrt(SQR(X[k] - X[j]) + SQR(Y[k] - Y[j]));
a=sqrt(SQR(X[k] - X[i]) + SQR(Y[k] - Y[i]));

if(a+b==c || a+c==b || b+c==a) continue;

p = (a+b+c)/2;
float s = sqrt(p*(p-a)*(p-b)*(p-c));

if(s < Smin) {
Smin = s;
min_1 = i, min_2 = j, min_3 = k;
}
}
}
}
cout << endl << "Smin = " << Smin << endl;
cout << "pnt 1: " << min_1 << " " << endl
<< "pnt 2: " << min_2 << " " << endl
<< "pnt 3: " << min_3 << endl;
getch();
return 0;
}
 К началу страницы 
+ Ответить 
сообщение
Сообщение #11


Пионер
**

Группа: Пользователи
Сообщений: 51
Пол: Мужской
Реальное имя: Владимир

Репутация: -  0  +


Все работает. Всем большое спасибо за помощь smile.gif
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #12


Michael_Rybak
*****

Группа: Пользователи
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Площадь, ИМО, лучше все-таки считать векторным произведением:

2s = (x3-x1)*(y2-y1) - (y3-y1)*(x2-x1)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 4:01
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name