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

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

Восстановить пароль Регистрация
 
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
11.12.2010, 09:34     Множество точек.Найти множество треугльники #1
ДАно 3n точек на плоскости , причем не какие три не лежат на одной прямой. Построить множество треугольников с вершинами в этих точках так что бы не какие 2 треугольника не пересекались и не содержали друг друга.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2010, 09:34     Множество точек.Найти множество треугльники
Посмотрите здесь:

C++ Дано множество точек. Найти медиану.
найти две наиболее удаленных друг от друга точки (множество точек задано на плоскости) C++
C++ на плоскости задано множество точек. Найти все подмножества точек, лежащих на одной прямой.
C++ Задано множество точек в трехмерном пространстве. Найти минимум радиусов шаров с центрами в этих точках, содержащих ровно n точек этого множества
C++ На плоскости задано множество точек. Выбрать три различные точки так, чтобы проходящая через них окружность делила это множество на группы
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 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");
    }
}
Выводит координаты точек треугольников. Вроде алгоритм верный. Берет левые точки для образования треугольников.
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
11.12.2010, 10:32  [ТС]     Множество точек.Найти множество треугльники #3
подскажи а что "qsort" делает???
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 2
11.12.2010, 11:46     Множество точек.Найти множество треугльники #4
Сортирует массив точек так, чтобы сначала шли точки с меньшим значением координаты x.
Alexlx
0 / 0 / 0
Регистрация: 28.11.2010
Сообщений: 25
11.12.2010, 14:31  [ТС]     Множество точек.Найти множество треугльники #5
а можно это как то без структуры сделать??
Евгений М.
1033 / 974 / 53
Регистрация: 28.02.2010
Сообщений: 2,817
Завершенные тесты: 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);
Yandex
Объявления
12.12.2010, 12:10     Множество точек.Найти множество треугльники
Ответ Создать тему
Опции темы

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