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

Дано n точек на плоскости - C++

Восстановить пароль Регистрация
 
Michanya
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 50
03.12.2010, 00:23     Дано n точек на плоскости #1
Указать (n-1)-звенную несамопересекающуюся незамкнутую ломанную проходящую через все эти точки. Число действий порядка n*log(n).
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.12.2010, 00:23     Дано n точек на плоскости
Посмотрите здесь:

C++ Дано несколько точек с целочисленными координатами. Определить максимальное количество точек из них, лежащих на одной прямой. Если можно напечатать н
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
Дано множество точек на плоскости C++
C++ Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек
C++ Среди заданных точек на плоскости найти ту, у которой расстояние суммы равно наибольшему от остальных точек
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.12.2010, 00:45     Дано n точек на плоскости #2
Алгоритм есть?
Michanya
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 50
03.12.2010, 00:55  [ТС]     Дано n точек на плоскости #3
алгоритма нету(
lemegeton
 Аватар для lemegeton
2909 / 1338 / 133
Регистрация: 29.11.2010
Сообщений: 2,720
03.12.2010, 01:21     Дано n точек на плоскости #4
Похоже, что задача на сортировку. Алгоритм сводится к тому, чтобы упорядочить точки по Х, при равных Х по У. Ну и все. Вывести на экран. Алгоритм STL sort реализует алгоритм быстрой сортировки, чья сложность в среднем случае как раз n*log(n).

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
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
class Point
{
public:
    int x, y;
    Point(void) 
    { 
        x = rand()%10+1; 
        y = rand()%10+1; 
    }
    bool operator< (const Point &compare)
    {
        return ((x == compare.x) ? y < compare.y : x < compare.x);
    }
};
 
int main()
{
    srand(static_cast<unsigned int>(time(0)));
 
    vector<Point> V(10);
 
    sort(V.begin(), V.end());
 
    for (vector<Point>::iterator i=V.begin(); i!=V.end(); i++)
        cout << "(" << i->x << ", " << i->y << ")" 
            << (((i+1)!=V.end())?" - ":"");
    cout << endl;
 
    system("pause");
}
Yandex
Объявления
03.12.2010, 01:21     Дано n точек на плоскости
Ответ Создать тему
Опции темы

Текущее время: 23:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru