Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 14, средняя оценка - 4.64
Adrian
0 / 0 / 0
Регистрация: 05.01.2009
Сообщений: 23
#1

Найти максимальный по площади выпуклый четырехугольник, который можно организовать из точек на плоскости - C++

05.01.2009, 16:34. Просмотров 1785. Ответов 7
Метки нет (Все метки)

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

з.ы. буду очень благодарен если откликнитесь...если можно хотя бы какую нибудь литературу посоветуйте...
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.01.2009, 16:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Найти максимальный по площади выпуклый четырехугольник, который можно организовать из точек на плоскости (C++):

Найти максимальный вес картошки, который можно унести в рюкзаке - C++
Найдите максимальный вес картошки, который можно унести в рюкзаке вместительностью s, если есть n картошин с заданными весами. Входные...

В заданном множестве точек плоскости найти количество точек в каждой из четвертей - C++
В заданном множестве точек плоскости найти количество точек в каждой из четвертей

В заданном множестве точек плоскости найти количество точек в каждой из четвертей - C++
В заданном множестве точек плоскости найти количество точек в каждой из четвертей. Знаете я не могу понять - а как задано это...

Из множества точек на плоскости найти точки, образующие параллелограмм с наибольшим количеством точек внутри - C++
"Даны N точек на плоскости. Найти среди них точки являющиеся вершинами фигуры, содержащей максимальное число заданных точек. Фигура -...

Среди заданных точек на плоскости найти ту, у которой расстояние суммы равно наибольшему от остальных точек - C++
Помогите вывести не цифру наибольшего значения, а все число. Задача: среди заданных точек на плоскости, найти ту у которой расстояние...

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

7
Vourhey
Почетный модератор
6486 / 2260 / 123
Регистрация: 29.07.2006
Сообщений: 12,635
05.01.2009, 16:35 #2
А для чего нам неопределенное количество точек, если у нас уже известно, что четырехугольник?
0
Adrian
0 / 0 / 0
Регистрация: 05.01.2009
Сообщений: 23
05.01.2009, 17:16  [ТС] #3
задача ставиться следующим образом :
задаются точки .допустим
а(1.3)
б(3.6)
с(1.6)
д(7.5)
е(8.3)

из этих точек можно организовать 4 четырехугольника:
абсд, аесд, абед, бсде

из этих четырехугольников нужно отобрать только те , которые являються выпуклыми

и далее задача сводиться к тому чтобы найти максимальный по площади четырехугольник
0
bmw666
9 / 7 / 1
Регистрация: 25.12.2008
Сообщений: 40
07.01.2009, 07:06 #4
Это совсем не сложно но долго.
сначала описываешь функцию для вычисления гипотенузы. Она понадобится для расчета расстояния между точками.
потом вызываешь эту функцию для каждой из пар точек.
после общитываешь себе площадь комбинаций этих отрезков. Вроде все.
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
#include <iostream.h>
#include <conio.h>
#include <math.h>
 
double Distance(int, int, int, int);
int main()
{
    int Points[2][5];
    double ab, ae, bc, be, cd, da, ea;
    for(int i=0; i<5; i++)//
    {
            cout << "Enter " << i+1 << " point:\nX: ";
            cin >> Points[0][i];
            cout << "Y: ";
            cin >> Points[1][i];
    }
    ab=Distance(Points[0][0], Points[1][0], Points[0][1], Points[1][1]);
    ae=Distance(Points[0][0], Points[1][0], Points[0][4], Points[1][4]);
    bc=Distance(Points[0][1], Points[1][1], Points[0][2], Points[1][2]);
    be=Distance(Points[0][1], Points[1][1], Points[0][4], Points[1][4]);
    cd=Distance(Points[0][2], Points[1][2], Points[0][3], Points[1][3]);
    da=Distance(Points[0][3], Points[1][3], Points[0][0], Points[1][0]);
    ea=Distance(Points[0][4], Points[1][4], Points[0][0], Points[1][0]);
    //...ГІГіГІ ìîæГ*Г® ïåðåáðГ*ГІГј ГўГ±ГҐ ñëó÷Г*ГЁ Г*Г® Гі ГІГҐГЎГї Г*Г*ГЇГЁГ±Г*Г*Г® Г·ГІГ® òîëüêî ГІГ*ГЄГЁГҐ.
    cout <<ab<<" "<<ae<<" "<<bc<<" "<<be<<" "<<cd<<" "<<da<<" "<<ea<< endl;
    getch();
    //...Г* Г¤Г*ëüøå Г±Г*Г¬ óæå ГЁГ№ГЁ ïëîùГ*äü.
}
double Distance(int Fx, int Fy, int Sx, int Sy)
{
    double res;
    res=sqrt(pow(Fx-Sx, 2)+pow(Fy-Sy, 2));
    return res;
}
Добавлено через 6 минут 35 секунд
В общем там остается только из сторон найти площадь.
0
Adrian
0 / 0 / 0
Регистрация: 05.01.2009
Сообщений: 23
07.01.2009, 10:44  [ТС] #5
ab=Distance(Points[0][0], Points[1][0], Points[0][1], Points[1][1]) а что эта функция делает? и вообще что то не совсем понял что за цифры после задания точек выводятся...обьясни пожалуйста, если не сложно..
0
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
07.01.2009, 12:08 #6
Цитата Сообщение от bmw666 Посмотреть сообщение
сначала описываешь функцию для вычисления гипотенузы
Гипотенуза - это сторона в прямоугольных треугольниках. а тут речь идут о выпуклых четырех угольниках. Т.е. не факт, что выбранные четыре точки организуют прямоугольник.
0
Adrian
0 / 0 / 0
Регистрация: 05.01.2009
Сообщений: 23
07.01.2009, 12:42  [ТС] #7
наверно не гипотинузы а диогонали...если найти диогональ но можно легко разбить четырехугольник на 2 треугольника
0
manfeese
129 / 128 / 16
Регистрация: 04.01.2009
Сообщений: 415
07.01.2009, 16:43 #8
Да тут ного вариантов решения, самое главное найти наиболее оптимальный!
0
07.01.2009, 16:43
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.01.2009, 16:43
Привет! Вот еще темы с ответами:

Найти выпуклый многоугольник с вершинами в некоторых точках из заданного множества точек на плоскости - Java SE
Задано множество точек на плоскости. Найти выпуклую оболочку этого множества, то есть выпуклый многоугольник с вершинами в некоторых точках...

Найти ромб наибольшей площади с вершинами в заданном множестве точек на плоскости. - Turbo Pascal
Доброго времени суток! НАйти ромб наибольшей площади с вершинами в заданном множестве точек на плоскости. Прошу помочь с задачей!

даны 10 точек на координатной плоскости, найти из них 3 таких точки, которые составят треугольник минимальной площади. - C++ Builder
Собственно сабж. Помогите любыми намётками, очень буду благодарна

Среди заданного на плоскости точек найти такую, сумма расстояний от который до остальных МАКСИМАЛЬНА - Pascal
Среди заданного на плоскости точек найти такую, сумма расстояний от который до остальных МАКСИМАЛЬНА!!!


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

Или воспользуйтесь поиском по форуму:
8
Ответ Создать тему
Опции темы

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