Египетские пирамиды

@Rusich22 · Регистрация: 09.01.2025

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

Задача B: Египетские пирамиды
Условие задачи (pdf)

Не только майя хотят строить пирамиды. Египтяне занимались этим до того, как это стало мэйнстримом.

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

Вообразите себя астрономом, а в Древнем Египте им давали все попадающиеся под руку задачи. По координатам проекций для каждого уровня определите, сколько уровней находится строго под ним.

Гарантируется, что для любых двух многоугольников один вложен в другой. Также никакие два многоугольника не пересекаются по периметру.

Формат входных данных
Первая строка входного файла содержит целое число
— количество многоугольников,
. Следующие
строк описывают
уровней-многоугольников.
–ая строка файла описывает
–ый многоугольник. Первое целое число
— количество вершин многоугольника,
. Последующие
пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от
до
.

Формат результата
Выведите единственную строку —
-ое число в ней должно быть равно числу уровней строго под
-м.

Примеры
Входные данные
3
3 -2 1 8 9 12 1
3 7 5 6 3 7 4
4 4 3 7 7 9 3 1 2
Результат работы
0 2 1

@Catstail · 10.01.2025, 18:50

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

Следующие
строк описывают
уровней-многоугольников.
–ая строка файла описывает
–ый многоугольник. Первое целое число
— количество вершин многоугольника,
. Последующие
пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от
до
.

- это на каком языке написано?

@u235 · 10.01.2025, 22:34

Очевидно, что нулевому уровню будет соответствовать самый большой по площади прямоугольник, следующему - поменьше, и т.д.
Т.е. предлагаю создать функцию вычисления площади полигона по координатам, используя
https://ru.m.wikipedia.org/wik... 1%81%D0%B0
Дальше останется только отсортировать полигоны, используя в качестве ключа эту функцию.

Добавлено через 2 часа 49 минут
Если ничего не напутал:

Python
1
2
3
4
5
6
7
8
9
10
11
12
def area(coords):
    coords+=coords[0:2] # Periodic boundary
    a1=sum(i*j for i,j in zip(coords[::2],coords[3::2]))
    a2=sum(i*j for i,j in zip(coords[1::2],coords[2::2]))
    return(abs(a1-a2)) # 2*area
poly_area=[]
n=int(input())
for i in range(n):
    k, *coords=map(int, input().split())
    poly_area.append((area(coords), i))
result=[i[1]  for i in sorted(poly_area, reverse=True)]
print(' '.join(map(str,result)))

@Aael · 13.01.2025, 14:44

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

Очевидно, что нулевому уровню будет соответствовать самый большой по площади прямоугольник

где-то видел эту задачу, там ограничение на модуль координат было 2·10⁹, соответственно, максимальная площадь 16·10¹⁸, что укладывается в 64 бита (usingned long long если на c++ писать), но т.к. некоторые площади могут быть полуцелыми, то для "удобного" хранения нужно 65 бит.. и автор предлагал вместо площадей выбрать наименьшую абсциссу от каждого моногоугольника и сортировать по ним, мол, "не пересекаются по периметру" отсекает случаи касания и прочего интересного..

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит переходные токи и напряжения на элементах схемы. . . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .

@Rusich22 0 / 0 / 0 Регистрация: 09.01.2025 Сообщений: 4

	Египетские пирамиды 10.01.2025, 16:20. Показов 1819. Ответов 3 Метки нет (Все метки) Задача B: Египетские пирамиды Условие задачи (pdf) Не только майя хотят строить пирамиды. Египтяне занимались этим до того, как это стало мэйнстримом. У египтян была более сложная схема — им надоели пирамиды с квадратным или прямоугольным основанием. Поэтому теперь каждый уровень пирамиды — произвольный многоугольник. Если представить пустыню в виде координатной плоскости и спроецировать на песок вершины каждого такого многоугольника пирамиды, то получатся просто вложенные друг в друга многоугольники на координатной плоскости. Вообразите себя астрономом, а в Древнем Египте им давали все попадающиеся под руку задачи. По координатам проекций для каждого уровня определите, сколько уровней находится строго под ним. Гарантируется, что для любых двух многоугольников один вложен в другой. Также никакие два многоугольника не пересекаются по периметру. Формат входных данных Первая строка входного файла содержит целое число — количество многоугольников, . Следующие строк описывают уровней-многоугольников. –ая строка файла описывает –ый многоугольник. Первое целое число — количество вершин многоугольника, . Последующие пар чисел — координаты вершин многоугольника в порядке его обхода. Координаты вершин — целые числа, принадлежащие диапазону от до . Формат результата Выведите единственную строку — -ое число в ней должно быть равно числу уровней строго под -м. Примеры Входные данные 3 3 -2 1 8 9 12 1 3 7 5 6 3 7 4 4 4 3 7 7 9 3 1 2 Результат работы 0 2 1 0