Карты Марса

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

Новые блоги и статьи Все статьи Все блоги /
Установка нескольких штампов электронной подписи в строго определенных местах файла docx ВладимирСамохин 19.07.2026 (В!) Работа с Электронной подписью - это неотъемлемая часть современного документооборота. Но что делать, если нужно поставить несколько штампов электронной подписи в строго определенных местах. . .	сукцессия 35. Научная статья о проделанной работе anaschu 19.07.2026 Написал в формате латекс и пдф	Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. Hrethgir 19.07.2026 Эта публикация сейчас в песочнице и ждёт приглашения. https:/ / habr. com/ ru/ sandbox/ 295048/ начало и оглавление - Как «пернатого» заставить осваивать новые горизонты опыта через масштабирование. . .	сукцессия 33. открытые вопросы от клауде anaschu 19.07.2026 "Что накопилось за эту часть А — тринадцать правок, из которых шесть пришли из ваших вопросов и каждая оказалась реальной ошибкой, а не калибровкой: односторонний симбиоз, отсутствующий листопад,. . .
32 сукцессия anaschu 19.07.2026 сукцессия 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не «подкручивает» сходимость —. . .	сукцессия 31: модель микоризы - это модель ещё нескольких явлений, социальных и экономических anaschu 18.07.2026 Теория «Всего»: апдейт v1. 1. 2 — 28‑мерное ядро стабилизировано Коллеги, фиксирую разбор инженерных правок и их изоморфную проекцию на экономику, меметику и половой отбор. Модель теперь не. . .	сукцессия 30. Массив проверяющих друг друга моделей anaschu 18.07.2026 Архитектура сети взаимопроверяющих моделей микоризной сукцессии (v2. 0) Развитие тензорного ОДУ-ядра и создание кросс-платформенного калибровочного полигона Уважаемые коллеги! В продолжение. . .	Грибы - это женщины, деревья - это мужчины. Анти инь янь для союза мужчины и женщины. anaschu 18.07.2026 ГЛАВНЫЙ НАУЧНО-ФИЛОСОФСКИЙ ВЫВОД: Сексуально-Репродуктивный Капитализм против Государства Моногамии Коллеги, мы вышли на финишную прямую 20-мерного ОДУ-моделирования вековой сукцессии (ветка. . .

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

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