Форум программистов, компьютерный форум, киберфорум
C (Си)
Войти
Регистрация
Восстановить пароль
Другие темы раздела
C (Си) вычисления суммы бесконечного ряда https://www.cyberforum.ru/ c/ thread2739457.html
Согласно индивидуального варианта составить вычисления суммы бесконечного ряда и программу для вычисления суммы бесконечного ряда, суммируя члены ряда, значения которых по модулю превышают заданную...
C (Си) Создание М-мерного дерева
Здравствуйте, хочу написать на СИ М-мерное дерево, чтобы один узел имел более двух потомков. Я написал создание вершины дерева, но совсем не понимаю, как написать потомков. Точнее примерно понимаю,...
Ищу книгу C (Си)
Здравствуйте все ! Я ищу книгу Джеймса Гренинга TDD для Embedded C, русский перевод. Купил английский вариант, но этот английский тяжел для меня. Если можно, дайте ссылку, желательно без...
C (Си) Ошибки при попытке чтения функций из другого файла файла Появилась необходимость сделать реализацию односвязного списка и использовать его из отдельного файла. Реализовал список, и создал файл .h со следующим кодом: #ifndef _LIST_H #define _LIST_H... https://www.cyberforum.ru/ c/ thread2735205.html
C (Си) Двовимірний массив https://www.cyberforum.ru/ c/ thread2734612.html
Допоможіть з масивом будь ласка! Таблиця символів Список складається з n рядків та 60 стовпців. Усі, кого ви знаєте, містять: назву місця та назву року, де рік є роком навчання і може дорівнювати...
C (Си) Ограничения fgets на кол-во символов
Есть функция fgets, которая читает строки из файла. И есть у нее аргументы: int fgets (char *str, int n, FILE *stream); str - указатель на массив, в который будет помещена считанная строка. n –...
C (Си) Формирование, обработка и печать одномерного массива
Написать программу для формирования, обработки и печати одномерного массива. В постановках задач нумерация индексов начинается с 1, но в Си-программе нумерация индексов должна начинаться с 0....
C (Си) Чтобы код выдавал привильную ошибку.(Шифр Цезаря) решает всё правильно, но почему то пробел она не считает за символ строки. Как можно сделать так, чтобы в строке мог быть и пробел? А так программа выдает ошибку 'ошибочная длина' если первая строка... https://www.cyberforum.ru/ c/ thread2734119.html
C (Си) Программа с легким циклом https://www.cyberforum.ru/ c/ thread2733165.html
Нужно составить программу, не понимаю как.
C (Си) Написать программу разложения функции в ряд Маклорена Нужна помощь(очень желательно, чтобы Вы смогли описать в двух-трех словах код) в написании программы на C, которая должна раскладывать ф-ию в ряд Маклорена. Ф-ия: f(x) = ln(1-x), a = 0. Заранее... https://www.cyberforum.ru/ c/ thread2732731.html
C (Си) Проблемы с выводом 0 https://www.cyberforum.ru/ c/ thread2732568.html
Привет ребята! Прошу у вас вас помощи.Задача такова: на ввод даются числа из различного количества цифр.Впереди может стоять знак + или -.Если минус,то выводим его,если плюс,то выводим число без...
C (Си) Не находит файл Помогите, очевидно проблема в пути к файлу, но как бы не менял исправить не удается, подскажите в чём может быть проблема #include <stdio.h> #include <conio.h> #include <locale> #include... https://www.cyberforum.ru/ c/ thread2732024.html
0 / 0 / 0
Регистрация: 29.11.2020
Сообщений: 1
0

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

29.11.2020, 15:55. Просмотров 1097. Ответов 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
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.