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

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

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

Множество точек.Найти множество треугльники - C++

11.12.2010, 09:34. Просмотров 582. Ответов 5
Метки нет (Все метки)

ДАно 3n точек на плоскости , причем не какие три не лежат на одной прямой. Построить множество треугольников с вершинами в этих точках так что бы не какие 2 треугольника не пересекались и не содержали друг друга.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2010, 09:34
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Множество точек.Найти множество треугльники (C++):

На плоскости заданы множество точек А и множество прямых В (каждая прямая задается значениями коэффициентов ур - C++
На плоскости заданы множество точек А и множество прямых В (каждая прямая задается значениями коэффициентов уравнения). Найти две такие...

На плоскости заданы множество точек А и множество прямых B - C++
На плоскости заданы множество точек А и множество прямых B. Найти две такие различные точки из А, чтобы проходящая через них прямая была...

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

Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества - C++
Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого...

Дано множество точек. Найти медиану. - C++
Учусь на первом курсе. Получил вот такое задание:"Медианой множества, состоящего из четного числа точек на плоскости, называется прямая,...

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

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
11.12.2010, 10:12 #2
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
/*
    Задача:
    Дано 3n точек на плоскости, причем не какие три не лежат на одной прямой.
    Построить множество треугольников с вершинами в этих точках так что бы не какие 2 треугольника не пересекались и не содержали друг друга. 
    
*/
 
#include <stdio.h>
#include <stdlib.h>
 
// Структура - точка
typedef struct _point
{
    float x;
    float y;
} point, *ppoint;
 
int compare (const void * a, const void * b)
{
    point p, q;
    p = *(point*)a;
    q = *(point*)b;
    if ( p.x > q.x ) return 1; else return -1;
}
 
int main()
{
    unsigned int n, i;
    point *a; // указатель на массив точек
    
    // Ввод n
    printf("n=");
    scanf("%u", &n);
    
    // Выделение массива для координат точек
    a = (point*)malloc(3*n*sizeof(point));
    for (i=0; i<3*n; i++)
    {
        printf("Vvedite koordinatu tochki #%u: ", i+1);
        scanf("%f %f", &a[i].x, &a[i].y);
    }
        
    qsort (a, 3*n, sizeof(point), compare);
    
    for (i=0; i<3*n; i+=3)
    {
        printf("Treugolnik #%u\n", i/3+1);
        printf("(%f,%f) ", a[i].x, a[i].y);
        printf("(%f,%f) ", a[i+1].x, a[i+1].y);
        printf("(%f,%f) ", a[i+2].x, a[i+2].y);
        printf("\n");
    }
}
Выводит координаты точек треугольников. Вроде алгоритм верный. Берет левые точки для образования треугольников.
0
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
11.12.2010, 10:32  [ТС] #3
подскажи а что "qsort" делает???
0
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
11.12.2010, 11:46 #4
Сортирует массив точек так, чтобы сначала шли точки с меньшим значением координаты x.
0
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
11.12.2010, 14:31  [ТС] #5
а можно это как то без структуры сделать??
0
Евгений М.
1035 / 976 / 54
Регистрация: 28.02.2010
Сообщений: 2,829
Завершенные тесты: 2
12.12.2010, 12:10 #6
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
#include <stdio.h>
#include <stdlib.h>
 
float *x, *y;
 
int compare (const void * a, const void * b)
{
    unsigned int p, q;
    p = *(unsigned int*)a;
    q = *(unsigned int*)b;
    if ( x[p] > x[q] ) return 1; else return -1;
}
 
int main()
{
    unsigned int n, i;
    
    unsigned int *a;
    
    // Ввод n
    printf("n=");
    scanf("%u", &n);
    
    // Выделение массива для координат точек
    x = (float *)malloc(3*n*sizeof(float));
    y = (float *)malloc(3*n*sizeof(float));
    a = (unsigned int *)malloc(3*n*sizeof(unsigned int));
    for (i=0; i<3*n; i++)
    {
        printf("Vvedite koordinatu tochki #%u: ", i+1);
        scanf("%f %f", &x[i], &y[i]);
        a[i]=i;
    }
    
    // Сортировка массива точек
    qsort (a, 3*n, sizeof(unsigned int), compare);
    
    // Вывод координат точек треугольников
    for (i=0; i<3*n; i+=3)
    {
        printf("Treugolnik #%u\n", i/3+1);
        printf("(%f,%f) ", x[a[i]], y[a[i]]);
        printf("(%f,%f) ", x[a[i+1]], y[a[i+1]]);
        printf("(%f,%f) ", x[a[i+2]], y[a[i+2]]);
        printf("\n");
    }
    
    free(x);
    free(y);
    free(a);
}
Добавлено через 1 минуту
Кстати, в коде со структурами я забыл написать
C
1
free(a);
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
12.12.2010, 12:10
Привет! Вот еще темы с ответами:

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

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

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

Дано множество точек на плоскости, заданных полярными координатами. Получить декартовы координаты этих точек - C++
Получилось сделать для координаты одной точки, а как сделать для множества точек, через цикл или массив? #include &lt;stdio.h&gt; #include...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
12.12.2010, 12:10
Ответ Создать тему
Опции темы

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