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

C++

Войти
Регистрация
Восстановить пароль
 
IceCortez
25 / 25 / 19
Регистрация: 25.03.2014
Сообщений: 233
#1

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

08.06.2016, 16:12. Просмотров 193. Ответов 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.
Кликните здесь для просмотра всего текста
Пытался сделать код более-менее читаемым
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
08.06.2016, 16:12     Задача Сок (Геометрия на плоскости)
Посмотрите здесь:

C++ геометрия
1) массивы 2)геометрия C++
Visual C++ геометрия на С++
Геометрия в С++. C++
C++ Геометрия
C++ геометрия
C++ Строки: Определить, сколько в тексте слов, в состав которых входит слог сок
C++ Написать программу, проверяющую, является ли частью данного слова слово 'сок'
C++ 1. Написать программу, проверяющую, является ли частью данного слова слово 'сок'
C++ Написать программу, проверяющую, является ли частью данного слова слово 'сок'
C++ Заметание плоскости. Вычислительная геометрия
Геометрия в С++ C++

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
vxg
Модератор
3067 / 1869 / 196
Регистрация: 13.01.2012
Сообщений: 7,110
10.06.2016, 09:53     Задача Сок (Геометрия на плоскости) #2
Цитата Сообщение от IceCortez Посмотреть сообщение
Но на каком-то тесте программа выдает неправильный ответ. Пытался подобрать этот тест или найти ошибку в коде, но не смог
очень плохо. если вы не смогли как мы сможем? и попутно вопрос: а была ли ошибка в таком случае
Yandex
Объявления
10.06.2016, 09:53     Задача Сок (Геометрия на плоскости)
Ответ Создать тему
Опции темы

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