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

Задача Сок (Геометрия на плоскости) - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Оценка сложности алгоритма http://www.cyberforum.ru/cpp/thread1757251.html
Здравствуйте! Помогите, пожалуйста, выполнить оценку сложности алгоритма игры крестики-нолики!!! Ниже исходник игры.. #include <iostream> #include <clocale> #include <windows.h> #include...
C++ Перепись с vb.net на плюсы Доброго времени суток, товарищи. Такой вопрос: получу ли я технологический профит, если перепишу программу, написанную на vb.net на платформу C++? Станет ли... Лучше? Или вообще как-либо изменится... http://www.cyberforum.ru/cpp/thread1757108.html
C++ Синоним для переменной структуры?
Предположим, есть структура сторонней библиотеки и ее переменная-член не соответсвует кодестайлу и нужно ввести синоним для этой переменной. Благодаря using или typedef мы можем ввести синоним для...
Битовые утечки при записи данных на диск C++
Доброго дня форумчане! Сорри если оффтоп но... Пишу в консольке на C++ (MSVCE 2010) различные движки по расчетам и тут столкнулся с опасной проблемой. При записи на диск искажаются данные на один...
C++ Builtin функции http://www.cyberforum.ru/cpp/thread1755256.html
Погружение в сабж. Компилятор gcc. Имеет ли смысл вообще их изучать, какие из них действительно надо знать, ибо полезные? И вообще, как можно относиться к их использованию в коде?
C++ Ищу исходники для игры pinball Всем Доброго времени суток ! Есть-ли у кого нибуть исходники для игры pinball (желательно с комментариями) ? Буду очень благодарен если кто-то скинет ! Добавлено через 33 секунды заранее... подробнее

Показать сообщение отдельно
IceCortez
25 / 25 / 19
Регистрация: 25.03.2014
Сообщений: 233

Задача Сок (Геометрия на плоскости) - C++

08.06.2016, 16:12. Просмотров 229. Ответов 1
Метки (Все метки)

С клавиатуры вводятся 2 числа: n и m.
Затем вводятся координаты n вершин выпуклого многоугольника в порядке обхода против часовой стрелки.
Затем вводятся m чисел - расстояние от 1 вершины до 1 дырки, расстояние от 1 дырки до 2, от 2 до 3 и т.д.
Можно любым образом поворачивать этот многоугольник.
Необходимо сделать это так, чтобы площадь части этого многоугольника, находящаяся ниже самой низкой дырки была как можно больше.
Моя идея: Переберем все пары соседних дырок и найдем площадь выпуклости между ними. Из всех таких возьмем максимум - это и есть ответ.
Написал код
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <cmath>
#include <cstdio>
#include <algorithm>
 
using namespace std;
 
#define sqr(a) (a)*(a)
#define double long double
 
struct point
{
    double x, y;
    point() { x = 0; y = 0; }
    point(double _x, double _y) { x = _x; y = _y; }
    void ger()
    {
        double r = x;
        double f = y;
        f = f / 180 * (acos((double)0) * 2);
        x = r * cos(f);
        y = r * sin(f);
    }
};
 
struct STRUCTvector
{
    double x, y;
    STRUCTvector(double _x, double _y) { x = _x; y = _y; }
    STRUCTvector(point a, point b)
    {
        x = b.x - a.x;
        y = b.y - a.y;
    }
};
 
double dist(point a, point b)
{
    return sqrt((double)(sqr(a.x - b.x)) + (double)(sqr(a.y - b.y)));
}
 
double len(STRUCTvector a)
{
    return sqrt((double)(a.x*a.x + a.y*a.y));
}
 
STRUCTvector multiply(STRUCTvector a, double k)
{
    a.x *= k;
    a.y *= k;
    return a;
}
 
STRUCTvector normal(STRUCTvector a)
{
    return multiply(a, 1 / len(a));
}
 
point add(point a, STRUCTvector b)
{
    return point(a.x + b.x, a.y + b.y);
}
 
double vecmult(STRUCTvector a, STRUCTvector b)
{
    return a.x * b.y - b.x * a.y;
}
 
double scalmult(STRUCTvector a, STRUCTvector b)
{
    return a.x * b.x + a.y * b.y;
}
 
double angle(STRUCTvector a, STRUCTvector b)
{
    return abs(atan2(vecmult(a, b), scalmult(a, b)));
}
 
int n, m, i, j;
point mas[100100];
point hole[100100];
double dhole[100100];
 
int main()
{
    //Ввод
    cin >> n >> m;
    //Костыль
    if (m == 1)
    while (true){}
 
    double P = 0;
    for (i = 0; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        mas[i] = point(x, y);
        if (i != 0)
            P += dist(mas[i], mas[i - 1]);
    }
    P += dist(mas[0], mas[n - 1]);
    for (i = 0; i < m; i++)
        cin >> dhole[i];
 
    //Находим координаты дыр
    i = 0;
    j = 0;
    double curs = 0, curholes = dhole[0];
    while (i < m)
    {
        //Находим вершину, после которой идет дырка
        while (curs + dist(mas[j], mas[(j + 1) % n]) < curholes)
        {
            curs += dist(mas[j], mas[(j + 1) % n]);
            j = (j + 1) % n;
        }
        //Формируем вектор
        STRUCTvector a(mas[j], point(mas[(j + 1) % n]));
        //Нормализуем его и откладываем от вершины
        a = normal(a);
        a = multiply(a, curholes - curs);
 
        hole[i] = add(mas[j], a);
        //Ищем следующую дырку
        i++;
        curholes += dhole[i];
    }
 
    i = 0;
    int l = 0, r = 0;
    double ld = 0, rd = 0, lhd = dhole[0], rhd = dhole[1] + lhd;
    double ans = -1;
    while (i < m)
    {
        //Двигаем указатель на левую вершину в промежутке между дырками
        while (true)
        {
            if (ld > lhd || abs(ld - lhd) < 0.0000000001)
                break;
            ld += dist(mas[l], mas[(l + 1) % n]);
            l = (l + 1) % n;
        }
 
        //Двигаем указатель на правую вершину в промежутке между дырками
        while (true)
        {
            if (rd + dist(mas[r], mas[(r + 1) % n]) > rhd)
                break;
            rd += dist(mas[r], mas[(r + 1) % n]);
            r = (r + 1) % n;
        }
 
        //Считаем площадь многоугольника
        double s = 0;
        s += vecmult(STRUCTvector(point(0, 0), hole[i]), STRUCTvector(point(0, 0), mas[l])) / 2;
 
        for (j = l; j != r; j = (j + 1) % n)
            s += vecmult(STRUCTvector(point(0, 0), mas[j]), STRUCTvector(point(0, 0), mas[(j + 1) % n])) / 2;
 
        s += vecmult(STRUCTvector(point(0, 0), mas[r]), STRUCTvector(point(0, 0), hole[(i + 1) % m])) / 2;
        s += vecmult(STRUCTvector(point(0, 0), hole[(i + 1) % m]), STRUCTvector(point(0, 0), hole[i])) / 2;
        ans = max(ans, abs(s));
 
        //Сдвигаем указатель на дырку и пересчитываем расстояния
        i++;
        lhd = rhd;
        rhd += dhole[(i + 1) % m];
        if (i == m - 1)
            rhd = P + dhole[0];
    }
 
    cout << ans;
 
    //system("pause");
}

Но на каком-то тесте программа выдает неправильный ответ. Пытался подобрать этот тест или найти ошибку в коде, но не смог, помогите понять, что не так.
P.S.
Кликните здесь для просмотра всего текста
Пытался сделать код более-менее читаемым
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru