Карты Марса

@MaFFFuH · Регистрация: 18.01.2022

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

ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ ПЖ

В 2051 году несколько экспедиций на Марс исследовали различные области красной планеты и сделали карты этих областей. Сейчас у BaSA (Балтийское Космическое Агенство) есть амбициозный план: они хотят произвести карту всей планеты. Чтобы подсчитать необходимые расходы, им нужно знать суммарную площадь областей, для которых карты уже есть. Ваша задача – написать программу, которая будет считать эту площадь.

Входные данные.

Ввод начинается со строки, содержащей целое число N (1<=N<=10000), количество доступных карт. Каждая из следующих N строк описывает одну карту. Каждая из этих строк содержит четыре целых числа x1, y1, x2 и y2 (0<=x1<x2<=30000, 0<=y1<y2<=30000). Значения (x1, y1) и (x2, y2) – координаты, соответственно, нижнего левого и правого верхнего углов карты. Каждая карта имеет прямоугольную форму, ее стороны параллельны осям OX и OY системы координат.

Выходные данные.

Выведите одно целое число A - суммарную исследованную площадь (то есть, площадь объединения всех прямоугольников).

Пример.

Для входных данных:

2
10 10 20 20
15 15 25 30
правильным ответом будет:

225

@eaa · 23.01.2022, 10:07

O(n^2):

Pascal
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
##
var rectangles := ArrGen(ReadInteger, i -> ReadInteger4);
 
var x := rectangles.SelectMany(i -> |i[0], i[2]|).ToSortedSet.ToArray;
var y := rectangles.SelectMany(i -> |i[1], i[3]|).ToSortedSet.ToArray;
 
var table := new integer[x.Count + 1, y.Count + 1];
foreach var (x1, y1, x2, y2) in rectangles do
begin
  var i1 := x.BinarySearch(x1);
  var j1 := y.BinarySearch(y1);
  var i2 := x.BinarySearch(x2);
  var j2 := y.BinarySearch(y2);
  table[i1, j1] += 1;
  table[i1, j2] -= 1;
  table[i2, j1] -= 1;
  table[i2, j2] += 1;
end;
 
for var i := 0 to x.Count do
  for var j := 0 to y.Count do
  begin
    if i > 0 then table[i, j] += table[i - 1, j];
    if j > 0 then table[i, j] += table[i, j - 1];
    if i * j > 0 then table[i, j] -= table[i - 1, j - 1]
  end;
 
var res: int64 := 0;
for var i := 0 to x.Count do
  for var j := 0 to y.Count do
    if table[i, j] > 0 then
      res += (x[i + 1] - x[i]) * (y[j + 1] - y[j]);
res.Print

можно дерево отрезков прикрутить.

@MaFFFuH · 01.02.2022, 21:05 **[ТС]**

Ограничение по времени и памяти, не принимает сайт задачу.

@Sun Serega · 01.02.2022, 21:07

И последний код от eaa тоже?
В любом случае, в первую очередь эти ограничения в студию.

@MaFFFuH · 01.02.2022, 21:13 **[ТС]**

Ограничение времени: 3 сек.
Ограничение памяти: 262144 КБайт

@eaa · 03.02.2022, 18:13

я же написал нужно дерево отрезков прикрутить тогда сложность будет O(n*logn)

Новые блоги и статьи Все статьи Все блоги /
Nekobox - outbounds[0].transport: unknown transport type: raw damix 01.10.2026 Фикс ошибки Правым кликом по серверу -> отладочная информация -> edit Заменить "net": "raw", на "net": "tcp", Нажать кнопку reload.	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .	Мобильное приложение ColorStep pavlinmavlin 17.09.2026 Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части Maks 13.09.2026 Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .	Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Jin X 06.09.2026 Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .	Программа опроса у.з. расходомера SLS-720F Argus19 02.09.2026 Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .	Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0. Maks 31.08.2026 При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42

	Карты Марса 18.01.2022, 20:38. Показов 1891. Ответов 24 Метки нет (Все метки) ПОМОГИТЕ РЕШИТЬ ЗАДАЧУ ПЖ В 2051 году несколько экспедиций на Марс исследовали различные области красной планеты и сделали карты этих областей. Сейчас у BaSA (Балтийское Космическое Агенство) есть амбициозный план: они хотят произвести карту всей планеты. Чтобы подсчитать необходимые расходы, им нужно знать суммарную площадь областей, для которых карты уже есть. Ваша задача – написать программу, которая будет считать эту площадь. Входные данные. Ввод начинается со строки, содержащей целое число N (1<=N<=10000), количество доступных карт. Каждая из следующих N строк описывает одну карту. Каждая из этих строк содержит четыре целых числа x1, y1, x2 и y2 (0<=x1<x2<=30000, 0<=y1<y2<=30000). Значения (x1, y1) и (x2, y2) – координаты, соответственно, нижнего левого и правого верхнего углов карты. Каждая карта имеет прямоугольную форму, ее стороны параллельны осям OX и OY системы координат. Выходные данные. Выведите одно целое число A - суммарную исследованную площадь (то есть, площадь объединения всех прямоугольников). Пример. Для входных данных: 2 10 10 20 20 15 15 25 30 правильным ответом будет: 225 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	01.02.2022, 21:05 [ТС]
	Ограничение по времени и памяти, не принимает сайт задачу. 0

@Sun Serega 2357 / 1460 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	01.02.2022, 21:07
	И последний код от eaa тоже? В любом случае, в первую очередь эти ограничения в студию. 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	01.02.2022, 21:13 [ТС]
	Ограничение времени: 3 сек. Ограничение памяти: 262144 КБайт 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	03.02.2022, 18:13
	я же написал нужно дерево отрезков прикрутить тогда сложность будет O(n*logn) 0