Карты Марса

@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)

Новые блоги и статьи Все статьи Все блоги /
сукцессия 43. Вторая научная статья за месяц- прайминг и гатгил anaschu 25.07.2026 две стороны одной монеты	Более приземисто - Эстафету хвоста в .cdl (деревья эстафеты в сад). Hrethgir 24.07.2026 В будущем, после написания блока инверсии обхода дерева (эстафеты хвоста), я планирую вернуться к нашему прошлому разговору о том, обладают ли знания целеполаганием. Тогда я пришел к выводу, что. . .	Вот представьте что вам дали бессмертие. kumehtar 24.07.2026 Вот представьте что вам дали бессмертие, ничего более не меняя. Вообще ничего, только бессмертие в нынешнем виде. Рады были бы? Что бы вы тут делали всё это время? Никакой пенсии. Никакого нового. . .	сукцессия 41 anaschu 24.07.2026 Численная верификация бифуркации в агентной модели лесной сукцессии: от одного параметра к ансамблю Автор: пользователь @Shumilov_AS \| Раздел: Прикладная математика / Численные методы Кратко. . .
сукцессия 40. Ансамблевая кластерная параметризаци, часть 1. anaschu 24.07.2026 Пр# Сопровождение научной статьи ИИ-ассистентом: подготовка публикации и калибровка агентно-ориентированной модели сукцессии микоризных систем Полевые заметки о двухнедельной совместной работе. . .	Теория всего 12. ВГК на планете в стратегической игре "терра" anaschu 21.07.2026 ### Главные семантические изменения и дешифровка новой физики 1. `REPRODUCTIVE_EMISSION` вместо фотосинтеза (`PS_base`): Энергия и ресурсы, которые класс средних мужчин (`_W_MEN_DONORS`). . .	Публикация отклонённая на хабре. Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование задачи и целеполагание Hrethgir 21.07.2026 https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11948&stc=1&d=1784657928 Привет Хабр. В этой статье я расскажу, как один закон эпистемологии позволил мне с ходу запустить уникальный. . .	Теория всего 11. Основные параметры anaschu 21.07.2026 Дешифровка тензорного ядра Soil Chemistry 2. 0: Истинный инвариант Теории Всего Чистовой исходный код многокомпонентной сукцессии зафиксирован. Модель оперирует единым вектором состояния. . .

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

	Карты Марса 18.01.2022, 20:38. Показов 1858. Ответов 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 2355 / 1458 / 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