Форум программистов, компьютерный форум, киберфорум
C (Си)
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/6: Рейтинг темы: голосов - 6, средняя оценка - 4.50
0 / 0 / 0
Регистрация: 29.11.2020
Сообщений: 1
1

Вывести координаты вершин выпуклой оболочки, отсортированные в порядке возрастания по их абсциссам

29.11.2020, 15:55. Просмотров 1078. Ответов 1
Метки нет (Все метки)

Всем привет! Первый раз на форуме, прошу не судить строго. Помогите, пожалуйста, с задачей на выпуклую оболочку. На ввод подается файл, в каждой строке которой есть 2 числа - координаты точек. В последней пустой строке только '\0'. Выводиться должны координаты вершин выпуклой оболочки, отсортированные в порядке возрастания по их абсциссам, если абсциссы равны, то сортировать следует по ординате. Спасибо!

Вот код программы:
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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define size 100
 
int location(int x1, int y1, int x2, int y2, int x3, int y3)
{
    if ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) > 0)
        return 1; //тчк нах-ся выше
    if ((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) < 0)
        return -1;//тчк нах-ся ниже
}
int distance(int x, int y, int A, int B, int C)
{
    return (abs(A * x + B * y + C) / sqrt(pow(A, 2) + pow(B, 2)));
}
void sort(int* VERT_x, int* VERT_y, int* vert_c)
{
    int i = 0, j = 0, temp = 0;
        for (int i = 0; i < *vert_c - 1; ++i)
        {
            for (j = *vert_c - 1; j > i; --j) 
            {
                if (VERT_x[j] > VERT_x[j + 1])
                {
                    temp = VERT_x[j];
                    VERT_x[j] = VERT_x[j + 1];
                    VERT_x[j + 1] = temp;
                }
                else
                    if (VERT_x[j] == VERT_x[j + 1])
                    {
                        if (VERT_y[j] < VERT_y[j + 1])
                        {
                            temp = VERT_x[j];
                            VERT_x[j] = VERT_x[j + 1];
                            VERT_x[j + 1] = temp;
                        }
                    }
            }
        }
}
 
int vertex(int upper_points_c, int* UPPER_points_x, int* UPPER_points_y, int x1, int y1, int x2, int y2, int* VERT_x, int* VERT_y, int* vert_c)
{
    if (upper_points_c == 0)
        return 0;
    else
    {
        int max_d = 0, max_d_x = 0, max_d_y = 0, i = 0;
        int new_upper_points_c1 = 0, new_upper_points_c2 = 0;
        int new_upper_X1[size] = { 0 };
        int new_upper_Y1[size] = { 0 };
        int new_upper_X2[size] = { 0 };
        int new_upper_Y2[size] = { 0 };
        int A = y1 - y2, B = x2 - x1, C = x1 * y2 - x2 * y1;//находим коэф-ты
        for (i = 0; i < upper_points_c; ++i)
        {
            if (distance(UPPER_points_x[i], UPPER_points_y[i], A, B, C) > max_d) //находим самую дальнюю точку
            {
                max_d = distance(UPPER_points_x[i], UPPER_points_y[i], A, B, C);
                max_d_x = UPPER_points_x[i];
                max_d_y = UPPER_points_y[i];
            }
        }
        for (i = 0; i < upper_points_c; ++i)
        {
            if (location(x1, y1, max_d_x, max_d_y, UPPER_points_x[i], UPPER_points_y[i]) == 1)//?????
            {
                new_upper_X1[new_upper_points_c1] = UPPER_points_x[i]; //если тчк выше прямой, то добавляем ее коорд-ты в массивы
                new_upper_Y1[new_upper_points_c1] = UPPER_points_y[i];
                ++new_upper_points_c1;
            }
            if (location(max_d_x, max_d_y, x2, y2, UPPER_points_x[i], UPPER_points_y[i]) == 1)//?????
            {
                new_upper_X2[new_upper_points_c2] = UPPER_points_x[i]; //если тчк выше прямой, то добавляем ее коорд-ты в массивы
                new_upper_Y2[new_upper_points_c2] = UPPER_points_y[i];
                ++new_upper_points_c2;
            }
        }
        if (new_upper_points_c1 != 0)//если есть вышележащие точки
        {
            vertex(new_upper_points_c1, new_upper_X1, new_upper_Y1, x1, y1, max_d_x, max_d_y, VERT_x, VERT_y, vert_c);
        }
        else
        {
            VERT_x[*vert_c] = max_d_x;
            VERT_y[*vert_c] = max_d_y;
            ++* vert_c;
        }
        if (new_upper_points_c2 != 0)//  --||--
        {
            vertex(new_upper_points_c2, new_upper_X2, new_upper_Y2, x2, y2, max_d_x, max_d_y, VERT_x, VERT_y, vert_c);
        }
        else
        {
            if (VERT_x[*vert_c - 1] != max_d_x && VERT_y[*vert_c - 1] != max_d_y)
            {
                VERT_x[*vert_c] = max_d_x;
                VERT_y[*vert_c] = max_d_y;
                ++* vert_c;
            }
        }
        return 1;
    }
}
 
int main()
{
    FILE* fr;
    int i = 0, points_c = 0, upper_points_c = 0, vert_c = 0;
    int UPPER_points_x[size] = { 0 };
    int UPPER_points_y[size] = { 0 };
    int LOWER_points_x[size] = { 0 };
    int LOWER_points_y[size] = { 0 };
    int lower_points_c = 0;
    int VERT_x[size] = { 0 };
    int VERT_y[size] = { 0 };
    char str[size] = { 0 };
    char temp_str[size] = { 0 };
    int X[size] = { 0 };
    int Y[size] = { 0 };
    fr = fopen("input.txt", "r");
    fgets(temp_str, size, fr);
    while (!feof(fr))//ввод данных
    {
        fgets(str, size, fr);
        sscanf(temp_str, "%d %d", &X[points_c], &Y[points_c]);
        ++points_c;
        if (strcmp(str, temp_str) != 0)
            strcpy(temp_str, str);
    }
    --points_c;
    int min_x = X[0], max_x = X[0], min_y=Y[0], max_y=Y[0]; 
    for (i = 0; i < points_c; ++i) //поиск стартовых точек
    {
        if (X[i] > max_x)
        {
            max_x = X[i];
            max_y = Y[i];
        }
        if (X[i] < min_x)
        {
            min_x = X[i];
            min_y = Y[i];
        }
    }
    VERT_x[vert_c] = min_x, VERT_y[vert_c] = min_y;
    ++vert_c;
    for (i = 0; i < points_c; ++i)
    {
        if (location(min_x, min_y, max_x, max_y, X[i], Y[i]) == 1)
        {
            UPPER_points_x[upper_points_c] = X[i];
            UPPER_points_y[upper_points_c] = Y[i];
            ++upper_points_c;
        }
        if (location(min_x, min_y, max_x, max_y, X[i], Y[i]) == -1)
        {
            LOWER_points_x[lower_points_c] = X[i];
            LOWER_points_y[lower_points_c] = Y[i];
            ++lower_points_c;
        }
    }
    vertex(upper_points_c, UPPER_points_x, UPPER_points_y, min_x, min_y, max_x, max_y, VERT_x, VERT_y, &vert_c);
    vertex(lower_points_c, LOWER_points_x, LOWER_points_y, min_x, min_y, max_x, max_y, VERT_x, VERT_y, &vert_c);
    VERT_x[vert_c] = max_x, VERT_y[vert_c] = max_y;
    sort(VERT_x, VERT_y, &vert_c+1);
    printf("Convex Hull is:\n");
    for (i = 0; i <= vert_c; ++i)
        printf("%d %d\n", VERT_x[i], VERT_y[i]);
    fclose(fr);
    return 0;
}
P.S В main упоминание "upper" относится к точкам, лежащим выше прямой, в в функции vertex под "upper" подразумеваются точки, лежащие во внешней полуплоскости относительно прямой.
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
29.11.2020, 15:55
Ответы с готовыми решениями:

Вычисляется количество вершин выпуклой оболочки, лежащих в 1-окрестности заданного заполненного треугольника
Вычисляется количество вершин выпуклой оболочки, лежащих в 1-окрестности заданного заполненного...

Вывести в консоли вершины выпуклой оболочки
Прошу помощи, не понимаю, не могу реализовать алгоритм Джарвиса и Грехэма - не понимаю. В консоли...

Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке, координаты
Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке,...

Вывести координаты вершин треугольника в порядке обхода по часовой стрелке
Здравствуйте. Не могли бы вы мне помочь с задачей,а то с геометрией я не очень дружу. Вот сама...

1
170 / 130 / 51
Регистрация: 18.07.2017
Сообщений: 684
30.11.2020, 19:50 2
Цитата Сообщение от KaizerloveRus Посмотреть сообщение
#define _CRT_SECURE_NO_WARNINGS
Варнинги включи. Или ты считаешь себя умнее разработчиков компилятора? Кто вас вообще учит их отключать?!!
Цитата Сообщение от KaizerloveRus Посмотреть сообщение
Вот код программы:
Лично мне лень проверять что работает правильно, а что нет (а кроме этого нужно еще и в предметную область вникнуть). Что именно не работает/работает неправильно?

Добавлено через 50 минут
C ходу вопросы:
1) ф-я location: У тебя неопределенное поведение когда координаты равны. Функция вернет мусор со стека, если вообще вернет. Также больше придирка, чем дельный совет: конструкция (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1) выполняется дважды, хотя результат не меняется. Уж лучше использовать переменную в таких случаях, может и не критичное место, но 3-4 свободных такта лишними не будут.
C++
1
2
3
4
5
6
int location(int x1, int y1, int x2, int y2, int x3, int y3){
    int result = (x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1);
    if (rezult > 0) return 1; //тчк нах-ся выше
    if (rezult < 0) return -1;//тчк нах-ся ниже
    return 0; // result = 0
}
Добавлено через 47 минут
2) Функция sort: Что за бардак? Определись с переменными! Выбрось лишнее из 21-22. Инициализировать переменные в 21 строке также не обязательно, так как они инициализируются позже и нигде не используются до инициализации (там их можно и объявить, а не в начале функции).
3) Функция vertex: Не удивительно, что в программу могла затесаться ошибка. У тебя 10 параметров передаются в функцию. Разбей на более мелкие функции, чтобы проще было отлаживать.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
30.11.2020, 19:50

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Вывести координаты вершин треугольника в порядке обхода по часовой стрелке
Заданы координаты вершин треугольника ABC на плоскости. Вывести их в порядке обхода по часовой...

Заданы координаты вершин четырехугольника. Вывести их в порядке обхода по часовой стрелке
Заданы координаты вершин четырехугольника. Вывести их в порядке обхода по часовой стрелке Сабж....

Заданы координаты вершин треугольника ABC на плоскости. Вывести их в порядке обхода по часовой стрелке
Заданы координаты вершин треугольника ABC на плоскости. Вывести их в порядке обхода по часовой...

BorlandC. Заданы координаты вершин треугольника ABC на плоскости. Вывести их в порядке обхода по часовой стрелке
BorlandC Задача 2.16. Заданы координаты вершин тре¬угольника ABC на плоскости. Вывести их в...

Массив: вывести на экран сначало положительные числа в порядке возрастания, а потом отрицательные в порядке возрастания.
Надо &quot;Создать динамический массив,заполнить случайными числами,затем вывести на экран сначало...

Заданы координаты вершин треугольника. Вывести их в порядке обхода треугольника по часовой стрелке
Заданы координаты вершин треугольника.Вывести их в порядке обхода треугольника по часовой стрелке....


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

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

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