Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.71/7: Рейтинг темы: голосов - 7, средняя оценка - 4.71
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689

Башни. Какие используются математические формулы?

08.01.2020, 13:39. Показов 1641. Ответов 12
Метки нет (Все метки)

Студворк — интернет-сервис помощи студентам
Согласно каким математическим формулам мы получаем верный ответ для каждой башни? Помогите разобраться в решении задачи!

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

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

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

Входные данные
В первой строке входного файла INPUT.TXT находится n (2 ≤ n ≤ 2000) - количество башен стены. В следующих n строках находятся натуральные числа xi и hi (0 ≤ xi ≤ 100000, 1 ≤ hi ≤ 10000) - координата и высота i-ой башни. Все xi различны.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать n строк. В i-ой строке выведите количество башен, которые видно из башни номер i.

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
#include <stdio.h>
#include <vector>
#include <algorithm>
 
struct Point
{
    int x;
    int y;
    int id;
    int ans;
};
 
 
int main() {
    int n;
    scanf("%d", &n);
    std::vector<Point> p(n);
    for (int i = 0; i < n; i++)                                                         {
        scanf("%d %d", &p[i].x, &p[i].y);
        p[i].id = i;
    }
    std::sort(p.begin(), p.end(), [](const Point &left, const Point &right) {
        return left.x < right.x;
    });
    for (int i = 0; i < n; i++) {
        int count = 0;
        {
            int maxdx = -1;
            int maxdy = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (maxdx == -1 || (p[j].y - p[i].y) * maxdx >= maxdy * (p[i].x - p[j].x)) {
                    count++;
                    maxdx = p[i].x - p[j].x;
                    maxdy = p[j].y - p[i].y;
                }
            }
        }
        {
            int maxdx = -1;
            int maxdy = -1;
            for (int j = i + 1; j < n; j++)
            {
                if (maxdx == -1 || (p[j].y - p[i].y) * maxdx >= maxdy * (p[j].x - p[i].x)) {
                    count++;
                    maxdx = p[j].x - p[i].x;
                    maxdy = p[j].y - p[i].y;
                }
            }
        }
        p[i].ans = count;
    }
    std::sort(p.begin(), p.end(), [](const Point &left, const Point &right)
    {
        return left.id < right.id;
    });
    for (int i = 0; i < n; i++)
    {
        printf("%d\n", p[i].ans);
    }
    return 0;
}
0
IT_Exp
Эксперт
34794 / 4073 / 2104
Регистрация: 17.06.2006
Сообщений: 32,602
Блог
08.01.2020, 13:39
Ответы с готовыми решениями:

Какие математические формулы используются в приведенных программах?
Учусь, студент , написали со знакомым две программы к курсовой, а преподавателдь требует еще и математические формулы . Вот программы может...

Записать математические формулы
Пожалуйста П.5.18.Правил Запрещено размещать задания и решения в виде картинок и других файлов с их текстом. ha=bsiny V=пR2H

Записать математические формулы
Полный код в С++ если знаете паскаль то в паскале тож.. спс

12
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
18.01.2020, 20:31  [ТС]
Ребят!
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.01.2020, 04:44
Задачка тривиальная, но авторы тестов подложили свинью там где не ожидаешь, в результате кот увеличился в 2 раза и потребовались приседания
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
#include <iostream>
#include <map>
 
const int N=2000;
int n, s[N], x[N], h[N];
 
int f(int j, int d) {
    int k=0, xm=0, hm=0;
    for (int i=j+d; i<n && i>=0; i+=d) {
        int hc=h[i]-h[j], xc=std::abs(x[i]-x[j]);
        if (hm*xc <= hc*xm) { k++; hm=hc; xm=xc; }
    }
    return k;
}
 
int main() {
    std::cin >> n; int p,q; std::map <int,std::pair<int,int>> m;
    for (int i=0; i<n; i++) { std::cin >> p >> q; m[p]=std::pair<int,int>(i,q); }
    int i=0;
    for (auto it = m.begin(); it != m.end(); ++it) {
        x[i]=(*it).first;
        h[i]=(*it).second.second;
        s[(*it).second.first]=i;
        i++;
    }
    for (int i=0; i<n; i++) std::cout << f(s[i], 1) + f(s[i], -1) << '\n';
}
Code
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
Тест    Результат  Время  Память
1   Accepted    0,015   424 Кб
2   Accepted    0,015   424 Кб
3   Accepted    0,015   424 Кб
4   Accepted    0,062   564 Кб
5   Accepted    0,015   424 Кб
6   Accepted    0,015   432 Кб
7   Accepted    0,015   432 Кб
8   Accepted    0,015   456 Кб
9   Accepted    0,015   456 Кб
10  Accepted    0,015   492 Кб
11  Accepted    0,015   492 Кб
12  Accepted    0,03    532 Кб
13  Accepted    0,062   564 Кб
14  Accepted    0,03    564 Кб
15  Accepted    0,03    568 Кб
16  Accepted    0,015   428 Кб
17  Accepted    0,015   432 Кб
18  Accepted    0,015   456 Кб
19  Accepted    0,03    492 Кб
20  Accepted    0,03    532 Кб
21  Accepted    0,03    564 Кб
22  Accepted    0,015   424 Кб
23  Accepted    0,015   432 Кб
24  Accepted    0,015   456 Кб
25  Accepted    0,062   492 Кб
26  Accepted    0,015   544 Кб
27  Accepted    0,03    564 Кб
28  Accepted    0,015   492 Кб
0
2734 / 889 / 331
Регистрация: 10.02.2018
Сообщений: 2,108
19.01.2020, 12:19
Башни. Какие используются математические формулы?
Я бы сказал, что используется векторное произведение. Но не целиком, а только его часть. По знаку определяется направление поворота между векторами. Первый вектор (max) - это направление на видимую башню. Второй вектор (p) - это направление на тестируемую.

https://www.cyberforum.ru/cgi-bin/latex.cgi?z = {max}_{x}\cdot {p}_{y} - {max}_{y}\cdot {p}_{x}
0
4949 / 2289 / 287
Регистрация: 01.03.2013
Сообщений: 5,991
Записей в блоге: 32
19.01.2020, 14:12
Мне хватило монотонности тангенса. Но по большому счету это одно и то же, конечно.
0
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
19.01.2020, 15:37  [ТС]
Ygg, что значит
Цитата Сообщение от Ygg Посмотреть сообщение
по знаку определяется направление поворота между векторами
?

Добавлено через 2 минуты
_Ivana, вы бы не могли прописать каждую строку кода ваших действий?
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
19.01.2020, 20:12
_Ivana, какие тесты? о чём ты?
0
2734 / 889 / 331
Регистрация: 10.02.2018
Сообщений: 2,108
19.01.2020, 20:27
Цитата Сообщение от Катя6 Посмотреть сообщение
что значит
Хотя, возможно, это не совсем верно. Это было бы справедливо, если бы угол лежал только в двух координатных четвертях (I и IV). Если подумать, то угол отсчитываемый против часовой стрелки от первого вектора ко второму может лежать во всех четырёх четвертях. Значит одного только знака синуса тут недостаточно. Приведённое вами решение точно корректно?

Добавлено через 7 минут
Цитата Сообщение от Ygg Посмотреть сообщение
Хотя, возможно, это не совсем верно.
Не, всё правильно, знак синуса вполне подходит. Что-то голова не варит уже под вечер
0
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
19.01.2020, 21:03  [ТС]
Ygg, я чет все-равно не понимаю, как мы получаем ответ
0
2734 / 889 / 331
Регистрация: 10.02.2018
Сообщений: 2,108
20.01.2020, 01:28
Свойство векторного произведения:
https://www.cyberforum.ru/cgi-bin/latex.cgi?{a}_{x}\cdot {b}_{y} - {a}_{y}\cdot {b}_{x} = a\cdot b\cdot sin(\alpha )

Отсюда можно выразить синус:
https://www.cyberforum.ru/cgi-bin/latex.cgi?sin(\alpha ) = \frac{{a}_{x}\cdot {b}_{y} - {a}_{y}\cdot {b}_{x}}{a\cdot b}

Первую башню всегда видно.
Дальше угол между векторами определяет видно следующую башню или нет.
Если угол меньше 180 градусов (синус больше 0), то башню видно.
Если угол больше 180 градусов (синус меньше или равен 0), то башню не видно.
Знаменатель формулы не влияет на знак синуса, так как он всегда больше 0.
Знак синуса определяется числителем.
Что бы определить знак числителя нужно сравнить уменьшаемое и вычитаемое.
Миниатюры
Башни. Какие используются математические формулы?  
0
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
20.01.2020, 13:12  [ТС]
Ygg, где в моем коде это все проверяется?
0
 Аватар для Kuzia domovenok
4268 / 3327 / 926
Регистрация: 25.03.2012
Сообщений: 12,531
Записей в блоге: 1
20.01.2020, 13:17
Ты писал код и не знаешь, что при этом там проверял?
Вот например эта и ещё подобная строчка что проверяет?
Не кажется ли, что именно эту формулу и проверя...
Цитата Сообщение от Катя6 Посмотреть сообщение
(p[j].y - p[i].y) * maxdx >= maxdy * (p[i].x - p[j].x)
0
0 / 0 / 0
Регистрация: 18.03.2019
Сообщений: 689
20.01.2020, 14:49  [ТС]
Kuzia domovenok, начнем с того, что я девочка...
А так, спасибо за помощь!
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
BasicMan
Эксперт
29316 / 5623 / 2384
Регистрация: 17.02.2009
Сообщений: 30,364
Блог
20.01.2020, 14:49
Помогаю со студенческими работами здесь

Как математические формулы записать
Первую формулу записал,а дальше не пойму. // zadanie_3.cpp: определяет точку входа для консольного приложения. // #include...

Написать математические формулы на языке C++
Всем привет. Задали описать математические формулы на C++. Я написал код, вот он: #include&quot;pch.h&quot; ...

Математические формулы, возведение в степень
Здравствуйте, я новичок в С++, интересует такой вопрос, я хочу чтобы программа выводила x2+7x+4.(именно в таком виде степень)

Какие математические функции используются в алгоритме шифрования RSA?
Столкнулся в тесте с таким вопросом, ответил возведение в степень и модуль, оказалось не правильно (наверное не все правильные выбрал, либо...

Какие математические функции используются в алгоритме шифрования RSA?
Столкнулся в тесте с таким вопросом, ответил возведение в степень и модуль, оказалось не правильно (наверное не все правильные выбрал, либо...


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

Или воспользуйтесь поиском по форуму:
13
Ответ Создать тему
Новые блоги и статьи
SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами
8Observer8 20.02.2026
Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .
Конвертировать закладки radiotray-ng в m3u-плейлист
damix 19.02.2026
Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI
Eddy_Em 18.02.2026
Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .
Камера Toupcam IUA500KMA
Eddy_Em 12.02.2026
Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .
И ясному Солнцу
zbw 12.02.2026
И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.
«Знание-Сила»
zbw 12.02.2026
«Знание-Сила» «Время-Деньги» «Деньги -Пуля»
SDL3 для Web (WebAssembly): Подключение Box2D v3, физика и отрисовка коллайдеров
8Observer8 12.02.2026
Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами и вызывать обработчики событий столкновения. . . .
SDL3 для Web (WebAssembly): Загрузка PNG с прозрачным фоном с помощью SDL_LoadPNG (без SDL3_image)
8Observer8 11.02.2026
Содержание блога Библиотека SDL3 содержит встроенные инструменты для базовой работы с изображениями - без использования библиотеки SDL3_image. Пошагово создадим проект для загрузки изображения. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru