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

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

Войти
Регистрация
Восстановить пароль
 
Michanya
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 50
#1

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

03.12.2010, 00:23. Просмотров 504. Ответов 3
Метки нет (Все метки)

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

Дано множество точек на плоскости - C++
Пожалуйста, если не сложно, нужен алгоритм с объяснением!! Заранее спасибо)) Дано множество точек на плоскости,заданных полярными...

Дано n точек на плоскости, за время n*logn построить (n-1)-звенную ломаную - C++
Дано n точек на плоскости, заданных своими декартовыми координатами. За время n*logn построить (n-1)-звенную не пересекающую себя ломаную,...

Дано множество точек на плоскости. Необходимо найти 4 точки (с максимальными и минимальными значениями x и y) - C++
Собственно, как я понял здесь нужна структура и динамический массив. но как это реализовать, я не знаю. Подскажите пожалуйста хотя бы как...

Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую - C++
Дано n точек на плоскости. Построить их выпуклую оболочку - минимальную выпуклую фигуру, их содержащую. (Резиновое колечко, натянутое на...

Множества точек на плоскости - C++
Помогите пожалуйста решить задачу ну или объясните принцип решения. Даны 2 множества точек на плоскости. Выбрать 3 различные точки...

Поиск точек на плоскости - C++
разработать объектно-ориентированную прогу для поиска пары наиболее близких точек из любого заданного набора точек на плоскости. Декартовые...

несколько точек на плоскости - C++
Дано несколько точек на плоскости с целыми координатами. Определить центр симметрии этого множества точек, если он существует

Множество точек на плоскости - C++
Даны 2 множества точек на плоскости. Выбрать 3 различные точки первого множества так , что бы треугольник с вершинами в этих точках...

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

Очередь, состоящая из точек координатной плоскости - C++
Доброго времени суток. Мне необходимо создать очередь, состоящую из пар чисел (х и у) и создать функции удаления, добавления элементов в...

Пусть даны коррдинаты n точек на плоскости - C++
Пусть даны коррдинаты n точек на плоскости x1,y1,...,xn,yn (n=20). Найти номера двух точек,расстояние между которыми наибольшее. (Считать...

Принадлежит ли точка множеству точек плоскости - C++
Принадлежность точки множеству Составить программу, которая определяет, принадлежит ли точка Z(X,Y) множеству точек плоскости, произведение...


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
03.12.2010, 00:45     Дано n точек на плоскости #2
Алгоритм есть?
Michanya
0 / 0 / 0
Регистрация: 21.11.2010
Сообщений: 50
03.12.2010, 00:55  [ТС]     Дано n точек на плоскости #3
алгоритма нету(
lemegeton
2918 / 1347 / 134
Регистрация: 29.11.2010
Сообщений: 2,721
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 точек на плоскости
Ответ Создать тему
Опции темы

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