Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/4: Рейтинг темы: голосов - 4, средняя оценка - 4.75
0 / 0 / 0
Регистрация: 30.01.2019
Сообщений: 3
1

пжста найдите ошибку в задаче на выпуклую оболочку

31.07.2019, 16:58. Показов 806. Ответов 3
Метки нет (Все метки)

Здравствуйте,уже 2 дня не могу найти ошибку в коде,валится на 5 тесте.
Задача:
Даны точки(их координаты).
Нужно построить выпуклую оболочку по этим точкам.
Вывод :
В первой строке нужно вывести количество точек в этой оболочке,
во второй нужно вывести сами точки в порядке обхода против часовой стрелки,
в третьей периметр оболочки ,с точностью до 9 знаков ,
в четвертой площадь.

Входные данные :
5
0 0
1 1
2 2
1 0
0 1

Выходные :
4
3 5 1 4
6.47213595499958000000
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
#include<iostream> 
#include<vector> 
#include<algorithm> 
#include<string> 
#include<set> 
#include<map> 
#include<iterator> 
#include<iomanip> 
#include<ctime> 
#include<deque>
#include<stack>
#include<queue>
#include<math.h> 
#include<cmath> 
using namespace std;
#pragma warning (disable:4996); 
#define lint long long 
#define endl '\n'
const long long INF = 1e17;
const long double eps = 0.00000000000001;
 
struct vec {
    lint x, y;
    vec(lint a, lint b) : x(a), y(b) {}
    long double len() {
        return sqrt(x * x + y * y);
    }
};
vector<vec>g;
vector<vec>st;
 
vec operator + (vec &a, vec &b) {
    return vec(a.x + b.x, a.y + b.y);
}
vec operator - (vec &a, vec &b) {
    return vec(a.x - b.x, a.y - b.y);
}
vec operator * (vec &a, long double k) {
    return vec(a.x * k, a.y * k);
}
lint operator % (vec &a, vec &b) {
    return a.x * b.y - b.x * a.y;
}
lint operator ^ (vec &a, vec &b) {
    return a.x * b.x + a.y * b.y;
}
vec vect(vec &a, vec &b) {
    return a - b;
}
lint vect1(vec &a, vec &b, vec&c, vec&d) {
    vec v1 = vect(a, b);
    vec v2 = vect(c, d);
    return v1 % v2;
}
bool comp(vec a, vec b) {
    vec a1(a.x - g[0].x, a.y - g[0].y);
    vec b1(b.x - g[0].x, b.y - g[0].y);
    if (a1%b1 > 0)return true;
    if (a1%b1 == 0)return a1.len() < b1.len();
 
    return 0;
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
#ifdef _DEBUG
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    long double a1, b1, c1, n, m, k, a2, b2, c2, a, b, c, d;
    cin >> n;
    lint xx, yy;
    map<pair<lint, lint>, lint>mp;
    for (int i = 0; i < n; ++i) {
        cin >> xx >> yy;
        vec vec1(xx, yy);
        g.push_back(vec1);
        mp[make_pair(xx, yy)] = i + 1;
    }
    lint miny = INF, minx = INF, index = 0;
    for (int i = 0; i < n; ++i) {
        if (g[i].x <= minx) {
            if (g[i].y < miny) miny = g[i].y;
            index = i;
            minx = g[i].x;
        }
    }
    swap(g[0], g[index]);
    sort(g.begin() + 1, g.end(), comp);
    st.push_back(g[0]);
    lint x11 = st[st.size() - 1].x, y11 = st[st.size() - 1].y;
    st.push_back(g[1]);
    st.push_back(g[2]);
    for (int i = 3; i < n; ++i) {
        if (g[i].x == st[st.size() - 1].x&&g[i].y == st[st.size() - 1].y)continue;
        while (st.size() > 1 && vect1(st[st.size() - 1], st[st.size() - 2], g[i], st[st.size() - 1]) <= 0ll)
        st.pop_back();
        st.push_back(g[i]);
    }
    cout << st.size() << endl;
    for (int i = 0; i < st.size(); ++i)
        cout << mp[make_pair(st[i].x, st[i].y)] << " ";
    cout << endl;
    long double sum = 0;
    vec vec1(x11, y11);
    st.push_back(vec1);
    vector<vec>st2 = st;
    while (!st.empty()) {
        lint xx = st[st.size() - 1].x;
        lint yy = st[st.size() - 1].y;
        st.pop_back();
        if (!st.empty())
            sum += sqrt((xx - st[st.size() - 1].x)*(xx - st[st.size() - 1].x) + (yy - st[st.size() - 1].y)*(yy - st[st.size() - 1].y));
    }
    cout << fixed << setprecision(10) << sum << endl;
 
    lint sum1 = 0;
    for (int i = 0; i < st2.size() - 1; ++i) 
        sum1 += st2[i] % st2[i + 1];
    sum1 += st2[st2.size() - 1] % st2[0];
    if (sum1 % 2 == 0)cout << sum1 / 2;
    else cout << sum1 / 2 << ".5";
    return 0;
}
Добавлено через 12 минут
насколько я понимаю,выпуклая оболочка и нахождение периметра строятся правильно,потому что до этого я сдал задачу на acmp на выпуклую оболочку на периметр и на площадь
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
31.07.2019, 16:58
Ответы с готовыми решениями:

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

Найти выпуклую оболочку множества
Задано множество N точек. Ai=1..N.Найти выпуклую оболочку этого множества,т.е. те точки,которые...

Найти выпуклую оболочку множества
Всем привет. Задача - найти выпуклую оболочку множества (крайние точки множества, образующие...

Построить выпуклую замкнутую оболочку
Построить выпуклую замкнутую оболочку y=1-x^(4/5)

3
6739 / 4537 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
31.07.2019, 17:18 2
Цитата Сообщение от nakazkan Посмотреть сообщение
lint miny = INF, minx = INF, index = 0;
А здесь точно должно быть INF? Может 0 или -INF?

Ну и, сделал бы const long long INF = std::numeric_limits<long long>::max();
0
0 / 0 / 0
Регистрация: 30.01.2019
Сообщений: 3
31.07.2019, 17:39  [ТС] 3
мне же нужно найти крайнюю точку ,а координаты 10 в 9 по модулю,я строю по самой левой нижней ,а значит она может быть (-1e9;-1e9)

Добавлено через 17 минут
ограничения :
количество точек 200000,координаты по модулю не превышают 10в9
0
6739 / 4537 / 1840
Регистрация: 07.05.2019
Сообщений: 13,725
Записей в блоге: 1
31.07.2019, 17:42 4
Цитата Сообщение от oleg-m1973 Посмотреть сообщение
А здесь точно должно быть INF? Может 0 или -INF?
А ну да, это ж минимум ищется, всё правильно
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
31.07.2019, 17:42

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

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

найдите ошибку в задаче
Помогите решить эту задачку: Список книг состоит из 10 записей. Запись содержит поля: фамилия...

Найдите ошибку в задаче
#include &quot;stdafx.h&quot; #include &quot;math.h&quot; #include &quot;iostream&quot; #include &quot;fstream&quot; #include...

Найдите ошибку в задаче: Определить процедуру вычисления площади треугольника по координатам его вершин
Даны натуральное число n, действительные числа x1, y1, x2, y2,…, xn,yn. Найти площадь...

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


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

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

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