Форум программистов, компьютерный форум CyberForum.ru

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

Войти
Регистрация
Восстановить пароль
 
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
#1

Алгоритм Грэхема - C++

18.05.2014, 12:00. Просмотров 628. Ответов 9
Метки нет (Все метки)

очень надо
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
18.05.2014, 12:00     Алгоритм Грэхема
Посмотрите здесь:

Алгоритм грэхема - C++
Добрые люди помогите пожалуйста. Есть код который выполняет алгоритм Грехема. Количество точек задаем сами. Если кол-во точек меньше 1000...

Алгоритм Грэхема - C++
Всем доброго времени суток На завтра надо уже принести алгоритм грэхема, но толком ничего не объяснил преподаватель Нашёл разные...

Алгоритм Грэхема, реализация на С++ - C++
Помогите написать реализацию Алгоритма на С++.

Реализация Алгоритма Грэхема и Джарвиса на С++ - C++
Ищу того, кто сделает за деньги с комментариями к каждой строке. В ЛС цену и за какое время.

Алгоритм Грэхема - Turbo Pascal
Помогите, пожалуйста составить Алгоритм Грэхема, есть такой код, но там ничего не понимаю struct pt { double x, y; }; bool cmp...

Построение минимальных выпуклых оболочек, алгоритм Грэхема - Python
Построение минимальных выпуклых оболочек. алгоритма Грэхема подскажите где ошибка. import _random def rotate(A,B,C): return...

.NET 4.x Где можно посмотреть реализацию алгоритма Джарвиса или Грэхема - C#
Здравствуйте. Кто-нить знает где можно посмотреть реализацию алгоритма Джарвиса или Грэхема на C#? Заранее благодарен!

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
18.05.2014, 12:02     Алгоритм Грэхема #2
https://code.google.com/p/polypuch/s...vex_graham.cpp
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
18.05.2014, 12:08  [ТС]     Алгоритм Грэхема #3
а есть попроще реализация?
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
18.05.2014, 12:10     Алгоритм Грэхема #4
Наверняка есть в гугле http://e-maxx.ru/algo/convex_hull_graham
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
18.05.2014, 12:12  [ТС]     Алгоритм Грэхема #5
этот нерабочий
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
18.05.2014, 12:23     Алгоритм Грэхема #6
Сообщение было отмечено автором темы, экспертом или модератором как ответ
Цитата Сообщение от Gmails Посмотреть сообщение
этот нерабочий
Не верю. Просто не умеете готовить.
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <algorithm>
#include <iostream>
#include <vector>
 
using namespace std;
 
struct pt {
    double x, y;
};
 
bool cmp (pt a, pt b) {
    return a.x < b.x || a.x == b.x && a.y < b.y;
}
 
bool cw (pt a, pt b, pt c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) < 0;
}
 
bool ccw (pt a, pt b, pt c) {
    return a.x*(b.y-c.y)+b.x*(c.y-a.y)+c.x*(a.y-b.y) > 0;
}
 
void convex_hull (vector<pt> & a) {
    if (a.size() == 1)  return;
    sort (a.begin(), a.end(), &cmp);
    pt p1 = a[0],  p2 = a.back();
    vector<pt> up, down;
    up.push_back (p1);
    down.push_back (p1);
    for (size_t i=1; i<a.size(); ++i) {
        if (i==a.size()-1 || cw (p1, a[i], p2)) {
            while (up.size()>=2 && !cw (up[up.size()-2], up[up.size()-1], a[i]))
                up.pop_back();
            up.push_back (a[i]);
        }
        if (i==a.size()-1 || ccw (p1, a[i], p2)) {
            while (down.size()>=2 && !ccw (down[down.size()-2], down[down.size()-1], a[i]))
                down.pop_back();
            down.push_back (a[i]);
        }
    }
    a.clear();
    for (size_t i=0; i<up.size(); ++i)
        a.push_back (up[i]);
    for (size_t i=down.size()-2; i>0; --i)
        a.push_back (down[i]);
}
 
int main() {
    std::vector<pt> a = {
        {2, 2},
        {3, 4},
        {1, 4},
        {2, 7},
        {4, 7},
        {5, 4},
        {5, 1},
        {7, 4}
    };
 
    convex_hull(a);
    for (const auto& pt : a) {
        std::cout << pt.x << " " << pt.y << std::endl;
    }
}
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
18.05.2014, 12:33  [ТС]     Алгоритм Грэхема #7
чет студия ругается на :for (const auto& pt : a)
и на это vector<pt> a = {
{2, 2},
{3, 4},
{1, 4},
{2, 7},
{4, 7},
{5, 4},
{5, 1},
{7, 4}
};-пишет такая инициализация не допускается
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
18.05.2014, 12:38     Алгоритм Грэхема #8
Конкретная версия студии может не поддерживать все возможности С++11.
Я предполагаю, что интуитивно ясно что тут происходит, и вполне можно самостоятельно заменить на аналогичный код. Наполнить вектор точками, переписать range-for на классический с итераторами.
Gmails
6 / 6 / 2
Регистрация: 08.04.2014
Сообщений: 248
18.05.2014, 12:47  [ТС]     Алгоритм Грэхема #9
for (const auto& pt : a)-данная интерпретация не ясна мне,пожалуйста объясните как ее заменить?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.05.2014, 12:50     Алгоритм Грэхема
Еще ссылки по теме:

Написание программы для нахождения выпуклой оболочки по алгоритму Грэхема - C#
Здравствуйте, пожалуйста помогите написать программу для нахождения ВО по алгоритму Грэхема. Точки задаются рандомно.

Реализация Алгоритма Грэхема на С++ - C++
Доброго времени суток, пожалуйста помогите разобраться с написанием программы. Что непонятно: 1) Каким образом вводятся точки? В...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...


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

Или воспользуйтесь поиском по форуму:
0x10
2459 / 1631 / 238
Регистрация: 24.11.2012
Сообщений: 4,012
18.05.2014, 12:50     Алгоритм Грэхема #10
Обход контейнера:
C++
1
2
3
for (std::vector<pt>::iterator it = a.begin(); it != a.end(); ++it) {
    std::cout << it->x << " " << it->y << std::endl;
}
Yandex
Объявления
18.05.2014, 12:50     Алгоритм Грэхема
Ответ Создать тему
Опции темы

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