Карты Марса

@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

@Sun Serega · 18.01.2022, 23:28

В идеале надо придумать алгоритм проверок, который не ломается если 3 области пересекаются.
Но я тупо выделил область памяти чтобы записывать, какие области 1х1 были обработаны.
Не эффективно по памяти, но пока входные карты маленькие - так даже эффективнее.

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
34
35
36
37
38
39
40
41
42
## function MarkReg(var reg: boolean): boolean;
begin
  Result := not reg;
  if not Result then exit;
  reg := true;
end;
 
var maps := ArrGen(ReadInteger, i->
begin
  var (x1,y1, x2,y2) := ReadInteger4;
  Result := new class(
    x1:=x1,x2:=x2,y1:=y1,y2:=y2,
    w:=x2-x1,h:=y2-y1
  );
end);
 
var res := maps[0].w*maps[0].h;
for var i := 1 to maps.Length-1 do
begin
  var m := maps[i];
  var new_regs := new boolean[m.w, m.h];
  res += new_regs.Length;
  
  foreach var m2 in maps.Take(i) do
  begin
    if m.x1>=m2.x2 then continue;
    if m.y1>=m2.y2 then continue;
    if m.x2<=m2.x1 then continue;
    if m.y2<=m2.y1 then continue;
    
    var s_x1 := Max(m.x1,m2.x1);
    var s_y1 := Max(m.y1,m2.y1);
    var s_x2 := Min(m.x2,m2.x2);
    var s_y2 := Min(m.y2,m2.y2);
    for var x := s_x1 to s_x2-1 do
      for var y := s_y1 to s_y2-1 do
        res -= integer(MarkReg(new_regs[x-m.x1,y-m.y1]));
    
  end;
  
end;
res.Println;

Добавлено через 5 минут
Или, ещё вариант, сделать что то типа алгоритма для сложения многоугольников, но упрощённого - потому что тут все стороны будут параллельны осям координат.
Хотя опять же, если проверочная программа не устроит стресс тест в виде входной карты 30000х30000 - это всё лишние усложения.

@MaFFFuH · 19.01.2022, 00:43 **[ТС]**

Спасибо большое, а можете еще решить через Record, а то сайт что то жалуется на данный код

@Sun Serega · 19.01.2022, 00:45

Какой компилятор стоит на том сайте?

Добавлено через 49 секунд
И "жалуется" это ни о чём, текст ошибок не для красоты придуман.

@MaFFFuH · 19.01.2022, 00:49 **[ТС]**

Не знаю что за компилятор, но вот что сайт выдает.
Ваша программа имеет неправильный синтаксис. Указанный компилятор не может создать выполняемой файл для вашей программы

Compile errors:
[1,4] z8becf.pas: Found 'function' but expected operator
‘Є®ЇЁа®ў ® д ©«®ў: 1.
Free Pascal Compiler version 3.0.0 [2015/11/16] for i386
Copyright (c) 1993-2015 by Florian Klaempfl and others
Target OS: Win32 for i386
Compiling z8becf_.pas
z8becf_.pas(1,1) Error: Illegal char constant
z8becf_.pas(1,1) Error: Illegal char constant
z8becf_.pas(1,3) Fatal: Syntax error, "BEGIN" expected but "const string" found
Fatal: Compilation aborted
Error: C:\FPC\bin\i386-win32\ppc386.exe returned an error exitcode

@Sun Serega · 19.01.2022, 00:50

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

Free Pascal Compiler

Ну так и какого вы делаете в разделе совершенно другого паскаля?
Раздел показывает сверху страницы.

@MaFFFuH · 19.01.2022, 00:53 **[ТС]**

У меня везде Pascal ABC.NET 3.0 показывает

@Sun Serega · 19.01.2022, 00:58

Где везде? Текст ошибки который вам выдал компилятор показывает Free Pascal.
Компилятор это то, что делает из текста программы .exe файл.
А редактировать код можно в чём угодно, хоть в ноутпеде.

Не по теме:

Версия 3.0 это что то очень древнее, в данном случае это не поможет, но лучше обновится:
http://pascalabc.net/ssyilki-dlya-skachivaniya

@MaFFFuH · 19.01.2022, 01:04 **[ТС]**

задача 625. Карты Марса
компилятор Pascal ABC.NET 3.0
Ошибка компиляции

@Sun Serega · 19.01.2022, 01:06

Я хз что будет на 3.0, я на 3.8.2:3056 писал.
Если на древнем PascalABC.Net не компилируется - ссылку на обновление я уже кинул.

@MaFFFuH · 19.01.2022, 01:19 **[ТС]**

Вот есть такое решение, но оно памяти занимает много слишком, поэтому сайт не принимает, надо чтобы в 4 раза меньше занимало. Там как то через Record делается, на я хз как

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
const nmax=30000;
type
  matrix = array [1..nmax, 1..nmax] of byte;
  
var
  a: matrix;
  i, j, n, m, x1, y1, x2, y2, s, k, l, w, g, h: integer;
 
begin
  g:=0;
  h:=0;
  begin
    readln(n);
    for i := 1 to n do
    begin
      read(x1, y1, x2, y2);
      if g<x2 then
            g:=x2;
          if h<y2 then
            h:=y2;
      for j := x1+1 to x2 do
        for m := y1+1 to y2 do 
          a[j, m] := 1;
    end;
  end;
  S := 0;
  for i:= 1 to g do
    for w:= 1 to h  do
      S := S + A[i, w];
  writeln(s);
end.

@Sun Serega · 19.01.2022, 01:24

Дело не в function вообще, вам на другое ругалось.

@MaFFFuH · 19.01.2022, 02:16 **[ТС]**

Да я код не понимаю, в этом проблема, в интернете такие себе обьяснения. Вот и прошу на более простом написать кого нибудь

@Sun Serega · 19.01.2022, 02:19

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

в интернете такие себе обьяснения

Опять же, где? Приводите точные данные, а не вот это вот.

В первую очередь надо смотреть на официальный сайт:
http://pascalabc.net/
Рекомендую начать с презентаций.

@MaFFFuH · 19.01.2022, 02:21 **[ТС]**

+ мы не проходили еще процедуры и функции, сдавать решение в таком виде слегка подозрительно будет

@XzzzX · 19.01.2022, 07:28

Не по теме:

MaFFFuH, ну дак тут надо предъявлять претензии к сайту. мало того, что они указывают версию pabc.net которую уже нигде не откопать скорее всего, дак ещё и компилируют другой системой

@Cyborg Drone · 21.01.2022, 23:12

MaFFFuH, выбирайте, куда перенести Вашу тему: в Pascal.ABC, Turbo Pascal или Free Pascal?

Можете, конечно, оставить тему здесь, но в разделе Pascal ABC.NET Вам и будут писать на Pascal ABC.NET, который Вы не знаете совершенно, и который не подходит для большинства проверочных сайтов.

Вы (ошибочно) считаете, что Вам нужна программа именно на Pascal ABC.NET, и она должна компилироваться на проверочном сайте. Вынужден Вас огорчить: Вы очень сильно заблуждаетесь.

Скорее всего, Вы не знаете разницы между Pascal ABC (без суффикса .NET, это антикварный учебный паскаль, предок Pascal ABC.NET) и Pascal ABC.NET (это современная мощная среда программирования, помесь Object Pascal и библиотеки классов Microsoft .NET FrameWork). Несмотря на схожие названия, это совершенно разные диалекты.

Синтаксис Pascal ABC.NET разительно отличается от синтаксиса прочих диалектов паскаля (в том числе, и от Pascal ABC), и программы, написанные именно для Pascal ABC.NET, в других диалектах паскаля не компилируются. Программу, написанные для других диалектов, практически всегда можно скомпилировать в Pascal ABC.NET, он достаточно всеяден.

На подавляющем большинстве проверочных сайтов используется Free Pascal. То, что на сайте написано, что он принимает программы на Pascal ABC.NET, не более чем замануха для тех, кого учат на дебилов. Такая дезинформация предназначена для накрутки рейтинга упомянутых сайтов (чтобы было больше посещений). Чаще всего программы и на самом деле компилируются, поскольку в школах для дебилов учат "классическому" синтаксису паскаля, который поддерживают все диалекты паскаля. Вот только Free Pascal не поддерживает синтаксиса Pascal ABC.NET, и поэтому когда сайту пытаются скормить программу, написанную именно для Pascal ABC.NET, он эту программу не может переварить по определению. Те, кто знает синтаксис Pascal ABC,NET, на такой сайт программу не отправят, а единичные случаи, типа Вашего, рейтинг не портят. Если сайту скормить программу на Pascal ABC (без .NET), то программа, скорее всего, скомпилируется, поскольку Pascal ABC и Free Pascal в плане синтаксиса отличаются незначительно.

Вас учат паскалю с "классическим" синтаксисом, это диалекты Pascal.ABC, Turbo Pascal и Free Pascal.

Вам не нужна программа на Pascal ABC.NET, поскольку синтаксису Pascal ABC.NET и присущим Pascal ABC.NET методам классов библиотеки Microsoft .NET FrameWork (всяким там методам работы с последовательностями и лямбда-выражениям) с вероятностью 99.9% Вас учить никогда не будут.

Я понятно всё объяснил? Если остались неясности, пишите, растолкую, что к чему. Итак, куда перенести тему?

И ещё. Вам предлагали в удалённых дублях этой темы ознакомиться с правилами форума. Ну так ознакомьтесь, пожалуйста, ссылка на правила есть на любой странице форума. Дублирование и кросспостинг тем запрещены. Если будете и далее плодить дублей, или умышленно нарушать другие правила форума, то с Вами могут поступить нехорошо.

@canadamoscow · 22.01.2022, 11:55

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type
  point = record x, y: integer;
  end;
 
begin
  var f := ReadAllLines('input.txt').ConvertAll(t -> t.toIntegers);
  var n := f[0, 0]; 
  var area := new hashset<point>; 
  for var koord := 1 to n do
  begin
    var (x1, y1, x2, y2) := f[koord];
    for var x := min(x1, x2) to max(x1, x2) - 1 do
      for var y := min(y1, y2) to max(y1, y2) - 1 do begin
        var p: point;
        (p.x, p.y) := (x, y);
        area.add(p);
      end;
  end;
  area.Count.Println
end.

@Sun Serega · 22.01.2022, 14:53

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

@eaa · 22.01.2022, 16:27

сканирующая прямая даст O(n^2).
добавить дерево отрезков можно добиться O(n*logn).

Новые блоги и статьи Все статьи Все блоги /
Жизнь в неопределённости kumehtar 23.03.2026 Жизнь — это постоянное существование в неопределённости. Например, даже если у тебя есть список дел, невозможно дойти до точки, где всё окончательно завершено и больше ничего не осталось. В принципе,. . .	Модель здравоСохранения: работники работают быстрее после её введения. anaschu 23.03.2026 geJalZw1fLo Корпорация до введения программа здравоохранения имела много невыполненных работниками заданий, после введения программы количество заданий выросло. Но на выплатах по больничным это. . .	1С: Контроль уникальности заводского номера Maks 23.03.2026 Алгоритм контроля уникальности заводского (или серийного) номера на примере документа выдачи шин для спецтехники с табличной частью. Данные берутся из регистра сведений, по которому настроено. . .	Хочу заставить корпорации вкладываться в здоровье сотрудников: делаю мат модель здравосохранения anaschu 22.03.2026 e7EYtONaj8Y Z4Tv2zpXVVo https:/ / github. com/ shumilovas/ med2. git
1С: Программный отбор элементов справочника по группе Maks 22.03.2026 Установка программного отбора элементов справочника "Номенклатура" из модуля формы документа. В качестве фильтра для отбора справочника служит группа номенклатуры. Отбор по наименованию группы. . .	Как я обхитрил таблицу Word Alexander-7 21.03.2026 Когда мигает курсор у внешнего края таблицы, и нам надо перейти на новую строку, а при нажатии Enter создается новый ряд таблицы с ячейками, то мы вместо нервных нажатий Энтеров мы пишем любые буквы. . .	Krabik - рыболовный бот для WoW 3.3.5a AmbA 21.03.2026 без регистрации и смс. Это не торговля, приложение не содержит рекламы. Выполняет свою непосредственную задачу - автоматизацию рыбалки в WoW - и ничего более. Однако если админы будут против -. . .	1С: Программный отбор элементов справочника по значению перечисления Maks 21.03.2026 Установка программного отбора элементов справочника "Сотрудники" из модуля формы документа. В качестве фильтра для отбора служит значение перечислений. / / Событие "НачалоВыбора" реквизита на форме. . .

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

	Карты Марса 18.01.2022, 20:38. Показов 1812. Ответов 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
	19.01.2022, 00:43 [ТС]
	Спасибо большое, а можете еще решить через Record, а то сайт что то жалуется на данный код 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	19.01.2022, 00:45
	Какой компилятор стоит на том сайте? Добавлено через 49 секунд И "жалуется" это ни о чём, текст ошибок не для красоты придуман. 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	19.01.2022, 00:53 [ТС]
	У меня везде Pascal ABC.NET 3.0 показывает 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	19.01.2022, 00:58
	Где везде? Текст ошибки который вам выдал компилятор показывает Free Pascal. Компилятор это то, что делает из текста программы .exe файл. А редактировать код можно в чём угодно, хоть в ноутпеде. Не по теме: Версия 3.0 это что то очень древнее, в данном случае это не поможет, но лучше обновится: http://pascalabc.net/ssyilki-dlya-skachivaniya 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	19.01.2022, 01:04 [ТС]
	задача 625. Карты Марса компилятор Pascal ABC.NET 3.0 Ошибка компиляции 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	19.01.2022, 01:06
	Я хз что будет на 3.0, я на 3.8.2:3056 писал. Если на древнем PascalABC.Net не компилируется - ссылку на обновление я уже кинул. 0

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	19.01.2022, 01:24
	Дело не в `function` вообще, вам на другое ругалось. 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	19.01.2022, 02:16 [ТС]
	Да я код не понимаю, в этом проблема, в интернете такие себе обьяснения. Вот и прошу на более простом написать кого нибудь 0

@MaFFFuH 2 / 2 / 1 Регистрация: 18.01.2022 Сообщений: 42
	19.01.2022, 02:21 [ТС]
	+ мы не проходили еще процедуры и функции, сдавать решение в таком виде слегка подозрительно будет 0

@XzzzX
	19.01.2022, 07:28
	Не по теме: MaFFFuH, ну дак тут надо предъявлять претензии к сайту. мало того, что они указывают версию pabc.net которую уже нигде не откопать скорее всего, дак ещё и компилируют другой системой 0

@Cyborg Drone Модератор 10445 / 5737 / 3406 Регистрация: 17.08.2012 Сообщений: 17,454
	21.01.2022, 23:12
	MaFFFuH, выбирайте, куда перенести Вашу тему: в Pascal.ABC, Turbo Pascal или Free Pascal? Можете, конечно, оставить тему здесь, но в разделе Pascal ABC.NET Вам и будут писать на Pascal ABC.NET, который Вы не знаете совершенно, и который не подходит для большинства проверочных сайтов. Вы (ошибочно) считаете, что Вам нужна программа именно на Pascal ABC.NET, и она должна компилироваться на проверочном сайте. Вынужден Вас огорчить: Вы очень сильно заблуждаетесь. Скорее всего, Вы не знаете разницы между Pascal ABC (без суффикса .NET, это антикварный учебный паскаль, предок Pascal ABC.NET) и Pascal ABC.NET (это современная мощная среда программирования, помесь Object Pascal и библиотеки классов Microsoft .NET FrameWork). Несмотря на схожие названия, это совершенно разные диалекты. Синтаксис Pascal ABC.NET разительно отличается от синтаксиса прочих диалектов паскаля (в том числе, и от Pascal ABC), и программы, написанные именно для Pascal ABC.NET, в других диалектах паскаля не компилируются. Программу, написанные для других диалектов, практически всегда можно скомпилировать в Pascal ABC.NET, он достаточно всеяден. На подавляющем большинстве проверочных сайтов используется Free Pascal. То, что на сайте написано, что он принимает программы на Pascal ABC.NET, не более чем замануха для тех, кого учат на дебилов. Такая дезинформация предназначена для накрутки рейтинга упомянутых сайтов (чтобы было больше посещений). Чаще всего программы и на самом деле компилируются, поскольку в школах для дебилов учат "классическому" синтаксису паскаля, который поддерживают все диалекты паскаля. Вот только Free Pascal не поддерживает синтаксиса Pascal ABC.NET, и поэтому когда сайту пытаются скормить программу, написанную именно для Pascal ABC.NET, он эту программу не может переварить по определению. Те, кто знает синтаксис Pascal ABC,NET, на такой сайт программу не отправят, а единичные случаи, типа Вашего, рейтинг не портят. Если сайту скормить программу на Pascal ABC (без .NET), то программа, скорее всего, скомпилируется, поскольку Pascal ABC и Free Pascal в плане синтаксиса отличаются незначительно. Вас учат паскалю с "классическим" синтаксисом, это диалекты Pascal.ABC, Turbo Pascal и Free Pascal. Вам не нужна программа на Pascal ABC.NET, поскольку синтаксису Pascal ABC.NET и присущим Pascal ABC.NET методам классов библиотеки Microsoft .NET FrameWork (всяким там методам работы с последовательностями и лямбда-выражениям) с вероятностью 99.9% Вас учить никогда не будут. Я понятно всё объяснил? Если остались неясности, пишите, растолкую, что к чему. Итак, куда перенести тему? И ещё. Вам предлагали в удалённых дублях этой темы ознакомиться с правилами форума. Ну так ознакомьтесь, пожалуйста, ссылка на правила есть на любой странице форума. Дублирование и кросспостинг тем запрещены. Если будете и далее плодить дублей, или умышленно нарушать другие правила форума, то с Вами могут поступить нехорошо. 1

@Sun Serega 2355 / 1458 / 526 Регистрация: 07.04.2017 Сообщений: 4,798
	22.01.2022, 14:53
	Множество позволяет быстро проверять элементы, но плохо подходит, если добавлять очень много элементов. Попробуйте ввести 1 карту максимального размера. Моя программа пыхтит но справляется, а ваша полностью задыхается. 0

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