В декартовой системе координат существует 4 прямоугольника, они могут пересекаться

@Prind · Регистрация: 28.09.2020

Студворк — интернет-сервис помощи студентам

В декартовой системе координат существует 4 прямоугольника, они могут пересекаться. На вход даётся 4 строчки с координатами x y левого нижнего и правого верхнего угла прямоугольников, все координаты по модулю не превосходят 1000. Нужно найти площадь, которую они занимают. Пересекающиеся области надо считать только один раз.
Пример :
Ввод :
3 1 6 3
1 2 4 7
2 4 6 8
5 2 7 6
Вывод :
35

Заранее спасибо! Пытался сам решить, но так и не придумал алгоритм.

@gunslinger · 27.08.2023, 01:02

https://photoshop-sklad.ru/kak... ugolnikov/

@XLAT · 27.08.2023, 12:22

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
#include <vector>
#include <sstream>
#include <iostream>
 
int main()
{
    auto s
    {   "3 1 6 3 "
        "1 2 4 7 "
        "2 4 6 8 "
        "5 2 7 6 "
    };
 
    std::stringstream i(s);
 
    auto m{std::vector(1000, std::string(1000, ' '))};
 
    for(unsigned a, b, c, d; i >> a >> b >> c >> d;)
    {   for    (unsigned y = b; y < d; ++y)
        {   for(unsigned x = a; x < c; ++x)
            {   m[y][x] = '.';
            }
        }
    }
 
    int res = 0;
 
    for    (const auto& r : m)
    {   for(const auto& c : r)
        {   if(c == '.')++res;
        }
    }
 
    std::cout << res;
}

@Prind · 27.08.2023, 14:26 **[ТС]**

Code
1
2
3
main.cpp:16:23: error: missing template arguments before ‘(’ token
   16 |     auto m{std::vector(1000, std::string(1000, ' '))};
      |

@XLAT · 27.08.2023, 14:35

Сообщение от Prind

main.cpp:16:23: error: missing template arguments before ‘(’ token
16 | auto m{std::vector(1000, std::string(1000, ' '))};

https://www.mycompiler.io/view/4M3JcKUNae8

@Prind · 27.08.2023, 14:57 **[ТС]**

Сообщение от XLAT

https://www.mycompiler.io/view/4M3JcKUNae8

Даже вижла ругается.

@Prind · 27.08.2023, 15:00 **[ТС]**

Вот скрин

@Prind · 27.08.2023, 15:09 **[ТС]**

странно, тестирующая система без ошибок скомпилировала

Добавлено через 7 минут
код выдаёт неверный ответ, забыл написать - числа могут быть отрицательными.

@XLAT · 27.08.2023, 15:12

Сообщение от Prind

Даже вижла ругается.

вы на острове, где не растёт кокос ...

В декартовой системе координат существует 4 прямоугольника, они могут пересекаться

эвакуируйтесь!

@XLAT · 27.08.2023, 15:15

Сообщение от Prind

код выдаёт неверный ответ, забыл написать - числа могут быть отрицательными.

я в курсе:

Сообщение от Prind

координаты по модулю не превосходят

но вы же программист - поправьте.

я вам, всего лишь, предложил саму идею.

@Prind · 27.08.2023, 15:29 **[ТС]**

хорошо, спасибо!

@igorrr37 · 27.08.2023, 16:48

Интересно было сделать для n прямоугольников

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
#include <iostream>
#include <numeric>
#include <ranges>
#include <vector>
#include <algorithm>
#include <cmath>
namespace rng = std::ranges;
 
// факториал
int fact(int n)
{
    return n ? n * fact(n - 1) : 1;
}
 
// C из n по k
int cnk(int n, int k)
{
    return fact(n) / (fact(k) * fact(n - k));
}
 
std::vector<std::vector<int>> vr, vtmp;
int n;
 
// находит пересечение двух прямоугольников va и vb
auto inter2(std::vector<int> const& va, std::vector<int> const& vb)
{
    std::vector<int> vret(4);
    int xa = std::clamp(va[0], vb[0], vb[2]);
    int xb = std::clamp(vb[0], va[0], va[2]);
    int ya = std::clamp(va[1], vb[1], vb[3]);
    int yb = std::clamp(vb[1], va[1], va[3]);
    if (xa == xb && ya == yb)
    {
        vret = { xa, ya, std::clamp(va[2], vb[0], vb[2]), std::clamp(va[3], vb[1], vb[3]) };
    }
    return vret;
}
 
int ind;
// для каждого сочетания из n по k пр-ков находит пересечение входящих в него пр-ков (всего n!/k!(n-k)! пересечений)
void interNK(int k)
{
    if (!k)
    {
        vr.push_back(vtmp.back());
    }
    else
    {
        for (int i = ind; i < n; ++i)
        {
            auto vicur = vtmp.empty() ? vr[i] : inter2(vr[i], vtmp.back());
            vtmp.push_back(vicur);
            ind = i + 1;
            interNK(k - 1);
            ind = 0;
            vtmp.pop_back();
        }
    }
}
 
int main()
{
    std::cin >> n;
    vr.resize(n);
    for (int i = 0; i < n; ++i)
    {
        std::copy_n(std::istream_iterator<int>{ std::cin }, 4, std::back_inserter(vr[i]));
    }
    for (int k = 2; k <= n; ++k)
    {
        interNK(k);
    }
 
    // общая площадь по формуле включений-исключений
    int ib = 0, sumTot{};
    for (int k = 1; k <= n; ++k)
    {
        int cnt = cnk(n, k);
        int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
        sumTot += k % 2 ? sum : -sum;
        ib += cnt;
    }
 
    std::cout << sumTot << "\n";
}
 
/*
4
0 0 2 2
1 1 3 3
1 0 5 3 
2 2 4 4
*/

@XLAT · 27.08.2023, 17:06

мне интересно в оверхед не завалится?

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
#include <vector>
#include <sstream>
#include <iostream>
 
const auto N{1000};
 
int main()
{
    std::istream* o = &std::cin;
 
    [[maybe_unused]]
    auto s{
        R"(
            3 1 6 3
            1 2 4 7
            2 4 6 8
            5 2 7 6
        )"
    };
 
    auto m{ std::vector(N + N, std::string(N + N, ' ')) };
 
                    /// std::stringstream i(s); o = &i;
 
                    for(int a, b, c, d; *o >> a >> b >> c >> d;)
                    {   for    (int y = b + N, D = d + N; y < D; ++y)
                        {   for(int x = a + N, C = c + N; x < C; ++x)
                            {   m[y][x] = '.';
                    }   }   }
 
    auto res{0};    for    (const auto& r : m)
                    {   for(const auto& c : r)
                        {   if(c == '.')++res;
                    }   }
 
    std::cout << res;
}

@Prind · 27.08.2023, 17:15 **[ТС]**

Сообщение от XLAT

мне интересно в оверхед не завалится?

оно у тебя впринципе всегда 0 выводит

Добавлено через 49 секунд

Сообщение от igorrr37

Интересно было сделать для n прямоугольников

main.cpp:7:22: error: ‘ranges’ is not a namespace-name
7 | namespace rng = std::ranges;
| ^~~~~~
main.cpp:25:1: error: ‘inter2’ function uses ‘auto’ type specifier without trailing return type
25 | auto inter2(std::vector<int> const& va, std::vector<int> const& vb)
| ^~~~
main.cpp:25:1: note: deduced return type only available with ‘-std=c++14’ or ‘-std=gnu++14’
main.cpp: In function ‘auto inter2(const std::vector<int>&, const std::vector<int>&)’:
main.cpp:28:19: error: ‘clamp’ is not a member of ‘std’
28 | int xa = std::clamp(va[0], vb[0], vb[2]);
| ^~~~~
main.cpp:29:19: error: ‘clamp’ is not a member of ‘std’
29 | int xb = std::clamp(vb[0], va[0], va[2]);
| ^~~~~
main.cpp:30:19: error: ‘clamp’ is not a member of ‘std’
30 | int ya = std::clamp(va[1], vb[1], vb[3]);
| ^~~~~
main.cpp:31:19: error: ‘clamp’ is not a member of ‘std’
31 | int yb = std::clamp(vb[1], va[1], va[3]);
| ^~~~~
main.cpp:34:31: error: ‘clamp’ is not a member of ‘std’
34 | vret = { xa, ya, std::clamp(va[2], vb[0], vb[2]), std::clamp(va[3], vb[1], vb[3]) };
| ^~~~~
main.cpp:34:64: error: ‘clamp’ is not a member of ‘std’
34 | vret = { xa, ya, std::clamp(va[2], vb[0], vb[2]), std::clamp(va[3], vb[1], vb[3]) };
| ^~~~~
main.cpp:34:91: error: no match for ‘operator=’ (operand types are ‘std::vector’ and ‘’)
34 | vret = { xa, ya, std::clamp(va[2], vb[0], vb[2]), std::clamp(va[3], vb[1], vb[3]) };
| ^
In file included from /usr/include/c++/11/vector:72,
from main.cpp:4:
/usr/include/c++/11/bits/vector.tcc:198:5: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(const std::vector<_Tp, _Alloc>&) [with _Tp = int; _Alloc = std::allocator]’
198 | vector<_Tp, _Alloc>::
| ^~~~~~~~~~~~~~~~~~~
/usr/include/c++/11/bits/vector.tcc:199:42: note: no known conversion for argument 1 from ‘’ to ‘const std::vector&’
199 | operator=(const vector<_Tp, _Alloc>& __x)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
In file included from /usr/include/c++/11/vector:67,
from main.cpp:4:
/usr/include/c++/11/bits/stl_vector.h:709:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::vector<_Tp, _Alloc>&&) [with _Tp = int; _Alloc = std::allocator]’
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move( ))
| ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:709:26: note: no known conversion for argument 1 from ‘’ to ‘std::vector&&’
709 | operator=(vector&& __x) noexcept(_Alloc_traits::_S_nothrow_move( ))
| ~~~~~~~~~^~~
/usr/include/c++/11/bits/stl_vector.h:730:7: note: candidate: ‘std::vector<_Tp, _Alloc>& std::vector<_Tp, _Alloc>::operator=(std::initializer_list <_Tp>) [with _Tp = int; _Alloc = std::allocator]’
730 | operator=(initializer_list<value_type> __l)
| ^~~~~~~~
/usr/include/c++/11/bits/stl_vector.h:730:46: note: no known conversion for argument 1 from ‘’ to ‘std::initializer_list’
730 | operator=(initializer_list<value_type> __l)
| ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~
main.cpp: In function ‘int main()’:
main.cpp:67:26: error: ‘istream_iterator’ is not a member of ‘std’
67 | std::copy_n(std::istream_iterator<int>{ std::cin }, 4, std::back_inserter(vr[i]));
| ^~~~~~~~~~~~~~~~
main.cpp:7:1: note: ‘std::istream_iterator’ is defined in header ‘’; did you forget to ‘#include ’?
6 | #include <cmath>
+++ |+#include <iterator>
7 | namespace rng = std::ranges;
main.cpp:67:43: error: expected primary-expression before ‘int’
67 | std::copy_n(std::istream_iterator<int>{ std::cin }, 4, std::back_inserter(vr[i]));
| ^~~
main.cpp:79:24: error: ‘reduce’ is not a member of ‘std’
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^~~~~~
main.cpp:79:86: error: use of ‘auto’ in lambda parameter declaration only available with ‘-std=c++14’ or ‘-std=gnu++14’
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^~~~
main.cpp: In lambda function:
main.cpp:79:118: error: invalid types ‘const int[int]’ for array subscript
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^
main.cpp:79:125: error: invalid types ‘const int[int]’ for array subscript
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^
main.cpp:79:134: error: invalid types ‘const int[int]’ for array subscript
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^
main.cpp:79:141: error: invalid types ‘const int[int]’ for array subscript
79 | int sum = std::reduce(vr.begin() + ib, vr.begin() + ib + cnt, 0, [](int sum, auto const& v) {return sum += (v[2] - v[0]) * (v[3] - v[1]); });
| ^

@igorrr37 · 27.08.2023, 17:32

Prind, https://onlinegdb.com/oVT_aRvri

@Prind · 27.08.2023, 17:49 **[ТС]**

igorrr37, всё, понял в чём у меня была проблема компиляции, сейчас попробую отправить в систему

@XLAT · 27.08.2023, 17:50

Сообщение от Prind

оно у тебя впринципе всегда 0 выводит

откуда

Сообщение от Prind

оно у тебя впринципе всегда 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
#include <vector>
#include <sstream>
#include <iostream>
 
const auto N{1000};
 
int main()
{
    std::istream* o = &std::cin;
 
    [[maybe_unused]]
    auto s{
        R"(
            3 1 6 3
            1 2 4 7
            2 4 6 8
            5 2 7 6
        )"
    };
 
    auto m{ std::vector(N + N, std::string(N + N, ' ')) };
 
                    /// std::stringstream i(s); o = &i;
 
                    for(int k = 4, a,   b,   c,   d; k != 0; --k)
                    {        *o >> a >> b >> c >> d;
                        for    (int y = b + N, D = d + N; y < D; ++y)
                        {   for(int x = a + N, C = c + N; x < C; ++x)
                            {   m[y][x] = '.';
                    }   }   }
 
    auto res{0};    for    (const auto& r : m)
                    {   for(const auto& c : r)
                        {   if(c == '.')++res;
                    }   }
 
    std::cout << res;
}

@Prind · 27.08.2023, 17:57 **[ТС]**

XLAT, да, тоже скомпилировало. У меня какой то баг был сегодня с вижлой, сейчас всё норм

@XLAT · 27.08.2023, 18:02

Сообщение от Prind

да, тоже скомпилировало.

я не про "скомпилировало"
я про:

Сообщение от Prind

код выдаёт неверный ответ

тест из шапки ГУД.

а дальше?

@Prind · 27.08.2023, 19:01 **[ТС]**

XLAT, как раз таки 0 выдавало из-за кривой компиляции

Добавлено через 58 минут
igorrr37, решение сдалось, ещё раз большое спасибо!
XLAT, вам тоже)

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Programma_Boinc 01.01.2026 Учёным и волонтёрам проекта «Einstein@home» удалось обнаружить четыре гамма-лучевых пульсара в джете Млечного Пути Сочетание глобально распределённой вычислительной мощности и инновационных. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .	Thinkpad X220 Tablet — это лучший бюджетный ноутбук для учёбы, точка. Programma_Boinc 23.12.2025 Рецензия / Мнение/ Перевод Нашел на реддите интересную статью под названием The Thinkpad X220 Tablet is the best budget school laptop period . Ниже её машинный перевод. Thinkpad X220 Tablet —. . .
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48

	В декартовой системе координат существует 4 прямоугольника, они могут пересекаться 26.08.2023, 23:41. Показов 1915. Ответов 21 Метки нет (Все метки) В декартовой системе координат существует 4 прямоугольника, они могут пересекаться. На вход даётся 4 строчки с координатами x y левого нижнего и правого верхнего угла прямоугольников, все координаты по модулю не превосходят 1000. Нужно найти площадь, которую они занимают. Пересекающиеся области надо считать только один раз. Пример : Ввод : 3 1 6 3 1 2 4 7 2 4 6 8 5 2 7 6 Вывод : 35 Заранее спасибо! Пытался сам решить, но так и не придумал алгоритм. 0

@gunslinger place status here 3186 / 2220 / 640 Регистрация: 20.07.2013 Сообщений: 6,010
	27.08.2023, 01:02
	https://photoshop-sklad.ru/kak... ugolnikov/ 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 15:00 [ТС]
	Вот скрин Миниатюры 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 15:09 [ТС]
	странно, тестирующая система без ошибок скомпилировала Добавлено через 7 минут код выдаёт неверный ответ, забыл написать - числа могут быть отрицательными. 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 15:29 [ТС]
	хорошо, спасибо! 0

@igorrr37 2870 / 2017 / 991 Регистрация: 21.12.2010 Сообщений: 3,733 Записей в блоге: 8
	27.08.2023, 17:32
	Prind, https://onlinegdb.com/oVT_aRvri 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 17:49 [ТС]
	igorrr37, всё, понял в чём у меня была проблема компиляции, сейчас попробую отправить в систему 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 17:57 [ТС]
	XLAT, да, тоже скомпилировало. У меня какой то баг был сегодня с вижлой, сейчас всё норм 0

@Prind 1 / 1 / 0 Регистрация: 28.09.2020 Сообщений: 48
	27.08.2023, 19:01 [ТС]
	XLAT, как раз таки 0 выдавало из-за кривой компиляции Добавлено через 58 минут igorrr37, решение сдалось, ещё раз большое спасибо! XLAT, вам тоже) 0

В декартовой системе координат существует 4 прямоугольника, они могут пересекаться

Решение