Живые точки

@mlsdmitry · Регистрация: 11.01.2020

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

Живые точки
Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
В IT-полигон одной из школ привезли 3D-биопринтер. Ученики напечатали на нём N точек и расположили на координатной плоскости. После этого точки ожили и начали играть в чехарду. Точка, которая делает ход, находит самую далёкую от себя точку на той же горизонтали или вертикали, где она находится, и перепрыгивает через неё на такое же расстояние. Если на одной горизонтали или вертикали с точкой не было других точек, то она остаётся на месте.
После завершения игры ученики выбирают две точки и строят прямоугольник со сторонами, параллельными осям координат, и вершинами в этих двух точках. Найдите его площадь.

Формат ввода
Программа получает на вход натуральное число N ≤ 1000 - количество точек. В следующих N строках записана пара целых чисел - координаты очередной точки, не превышающие по модулю 109. Дальше идёт строка с номерами точек, записанными в порядке их ходов. Если от точки одинаковое максимальное расстояние до нескольких других точек, то выбирается расположенная на одной горизонтали. Если две точки одинаково далеко удалены по одной оси, то выбирается та, которая уменьшает соответствующую координату. В последней строке вводятся два числа - номера точек, которые должны образовать прямоугольник.

Формат вывода
Программа должна вывести одно число - площадь прямоугольника. Если прямоугольник образовать невозможно, программа должна вывести число 0.

Пример 1
Ввод Вывод
4
1 2
1 3
4 3
4 1
2 4
4 1
9
Пример 2
Ввод Вывод
3
1 2
2 1
3 1
1 1 1 2 2 3 1
2 1
Мой код, работает, но набирает 6.7/10
Нужна помощь, где-то ломается логика. Код в файле
Так же остальные два файла[Живые точки.txt и input.txt] для удобного тестирования
Живые точки.txt и prod.txt переименовать в .py
Заранее спасибо за помощь

@Manwithoutname · 14.01.2020, 20:28

Короч, есть два кода. Длинный, но веселый и короткий, но скучный... И ОБА КОДА НЕ МОГУТ ПРОЙТИ ОГРАНИЧЕНИЕ ПО ВРЕМЕНИ!!! КАААААААААААААААААААААААК, почему, зачем...

@pskobx · 14.01.2020, 20:39

буду благодарен если скинешь

@Manwithoutname · 14.01.2020, 20:43

А если честн, то скок у вас баллов? Прост я не могу понять, хоть кто-нибудь знает, что они в итоге дадут?

@pskobx · 14.01.2020, 20:50

имеешь ввиду баллов за задачу?

@Manwithoutname · 14.01.2020, 20:55

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

имеешь ввиду баллов за задачу?

за задачу и в сумме за все задания

@pskobx · 14.01.2020, 20:58

в сумме - 45. а за эту задачу еще 0, только час назад про нее вспомнил(

@Manwithoutname · 14.01.2020, 21:03

Скоро скину. Пытаюсь все-таки выйти на 10

@pskobx · 14.01.2020, 21:14

а у тебя то сколько баллов в сумме?

@Manwithoutname · 14.01.2020, 21:17

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

а у тебя то сколько баллов в сумме?

В том-то и дело, что 50. Еще бы вчера покончил с этой задачей, если бы не такое идиотское ограничение по времени

@pskobx · 14.01.2020, 21:21

если еще не сделал - можно весь код засунуть в def, а потом эту функцию вызвать, может 0.3 - 0.5 сек сэкономит

@Manwithoutname · 14.01.2020, 21:39

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

если еще не сделал - можно весь код засунуть в def, а потом эту функцию вызвать, может 0.3 - 0.5 сек сэкономит

не сработало( странно, по идее должно. Ща скину код короткий, будем думать вместе

Добавлено через 5 минут

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
coor = []
for _ in range(n):
    coor.append([int(i) for i in input().split()])
ex = [int(i) - 1 for i in input().split()]
for i in ex:
    px, py = coor[i][0], coor[i][1]
    kxcoor = [[0, j[0], abs(j[0] - px)] for j in coor if j[1] == py and j[0] != px] + \
             [[1, j[1], abs(j[1] - py)] for j in coor if j[0] == px and j[1] != py]
    if kxcoor:
        kxcoor.sort(key=lambda q: (q[2], -q[1], -q[0]))
        w = kxcoor[-1]
        if w[1] <= coor[i][w[0]]:
            coor[i][w[0]] = w[1] - w[2]
        else:
            coor[i][w[0]] = w[1] + w[2]
x, y = map(int, input().split())
print(abs(coor[x - 1][0] - coor[y - 1][0]) * abs(coor[x - 1][1] - coor[y - 1][1]))

@pskobx · 14.01.2020, 21:39

окей, жду

@Manwithoutname · 14.01.2020, 21:39

Давайте думать, господа. Еще два часа. Должен найтись хоть какой-то гений

@pskobx · 14.01.2020, 21:40

так, сейчас взгляну...

@Manwithoutname · 14.01.2020, 21:43

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

так, сейчас взгляну...

Понимаю, выглядит не оч, но что имею) занятия полгода идут ток, а я уже половину уроков пропустил, так как здоровье хиленькое. Если есть советы, то я к вашему вниманию :)

@pskobx · 14.01.2020, 21:47

лямбда функций вроде не было еще))

@Manwithoutname · 14.01.2020, 21:50

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

лямбда функций вроде не было еще))

Знаю, но когда копался в способах сортировки, то обнаружил это) А для быстрого решения заданий перед дедлайном 9 января, когда у тебя 34 задания еще не сделано, это оч удобная вещь.

@mlsdmitry · 14.01.2020, 21:57 **[ТС]**

На вскидку могу сказать, напиши нормальный обычный цикл для 8-9 строчки. И тебе не придется делать их два, один будет быстрее.

@Manwithoutname · 14.01.2020, 22:02

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

На вскидку могу сказать, напиши нормальный обычный цикл для 8-9 строчки. И тебе не придется делать их два, один будет быстрее.

оп, спасибо, ща попробую. А ты тоже наш товарищ по несчастью или добрый прохожий?)

@mlsdmitry · 14.01.2020, 22:04 **[ТС]**

Я создатель темы

Новые блоги и статьи Все статьи Все блоги /
Кто убил Suno? Почему наше солнышко погасло? (диалог с ИИ Джемени) zorxor 30.10.2026 Как убивали Suno. Хронология. «Убийство» музыкальной нейросети Suno — это затяжной процесс, в котором технологический хайп стартапа разбился о жесткую реальность судебных исков от гигантов. . .	Генератор паролей (вариант №2) Maks 30.10.2026 Обновленная версия ранее созданной обработки. Добавлены следующие реквизиты типа Булево: - Буквы; - Цифры; - Символы. Изменена логика команды "Сгенерировать" и процедуры "ПриОткрытии":. . .	Генератор паролей (вариант №1) Maks 29.10.2026 Реализация из решения ниже выполнена исключительно по моей инициативе, дабы облегчить себе работу в создании паролей для администрируемых мною сервисов и пользователей. Самым главным критерием для. . .	Установка ChatGPT (Codex) на Windows без использования Microsoft Store Fabien159 28.10.2026 Здравствуйте всем читающим! Опишу процесс установки ChatGPT (Codex) на Windows, если по каким-то причинам у вас не получается устанавить его через Microsoft Store. И так: 1. Скачиваем с. . .
Программное добавление префикса в нумерацию документов Maks 27.10.2026 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .	После закрытия оутлука продолжает висеть процесс в диспетчере задач Maks 27.10.2026 С недавнего времени в продакшене возникла проблема: при закрытии оутлука в диспетчере задач продолжал висеть процесс outlook. exe. Проблема возникла после установки MS Office 2021 LTSC на машинах, под. . .	Baragoz - DPS/HPS бот для WoW 3.3.5a, многоязычный AmbA 26.10.2026 Хотите ещё ботов? У меня есть один! А я пока отдохну от него. https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=12062&stc=1&d=1793007952 Инструкция внутри. https:/ / youtu. be/ VpfFZSUDGnQ. . .	Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 20:28
	Короч, есть два кода. Длинный, но веселый и короткий, но скучный... И ОБА КОДА НЕ МОГУТ ПРОЙТИ ОГРАНИЧЕНИЕ ПО ВРЕМЕНИ!!! КАААААААААААААААААААААААК, почему, зачем... 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 20:39
	буду благодарен если скинешь 0

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 20:43
	А если честн, то скок у вас баллов? Прост я не могу понять, хоть кто-нибудь знает, что они в итоге дадут? 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 20:50
	имеешь ввиду баллов за задачу? 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 20:58
	в сумме - 45. а за эту задачу еще 0, только час назад про нее вспомнил( 0

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 21:03
	Скоро скину. Пытаюсь все-таки выйти на 10 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 21:14
	а у тебя то сколько баллов в сумме? 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 21:21
	если еще не сделал - можно весь код засунуть в def, а потом эту функцию вызвать, может 0.3 - 0.5 сек сэкономит 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 21:39
	окей, жду 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 21:40
	так, сейчас взгляну... 0

@pskobx 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 10
	14.01.2020, 21:47
	лямбда функций вроде не было еще)) 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 21:57 [ТС]
	На вскидку могу сказать, напиши нормальный обычный цикл для 8-9 строчки. И тебе не придется делать их два, один будет быстрее. 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:04 [ТС]
	Я создатель темы 0