Живые точки

@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 **[ТС]**

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

Новые блоги и статьи Все статьи Все блоги /
Асинхронный приём данных из COM-порта Argus19 01.05.2026 Асинхронный приём данных из COM-порта Купил на aliexpress термопринтер QR701. Он оказался странным. Поключил к Arduino Nano. Был очень удивлён. Наотрез отказывается печатать русские буквы. Чтобы. . .	попытка написать игровой сервер на C++ pyirrlicht 29.04.2026 попытка написать игровой сервер на плюсах с открытым бесконечным миром. возможно получится прикрутить интерпретатор питон для кастомизации игровой логики. что есть на текущий момент:. . .	Контроль уникальности выбранного документа-основания при изменении реквизита Maks 28.04.2026 Алгоритм из решения ниже разработан на примере нетипового документа "ЗаявкаНаРемонтСпецтехники", разработанного в КА2. Задача: уведомлять пользователя, если указанная заявка (документ-основание). . .	Благородство как наказание Maks 24.04.2026 У хорошего человека отношения с женщинами всегда складываются трудно. А я человек хороший. Заявляю без тени смущения, потому что гордиться тут нечем. От хорошего человека ждут соответствующего. . .
Валидация и контроль данных табличной части документа перед записью Maks 22.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в КА2. Задача: контроль и валидация данных табличной части документа перед записью с учетом регламента компании. . .	Отчёт о затраченных материалах за определенный период с макетом печатной формы Maks 21.04.2026 Отчёт из решения ниже размещён в конфигурации КА2. Задача: разработка отчёта по затраченным материалам за определённый период, с возможностью вывода печатной формы отчёта с шапкой и подвалом. В. . .	Отчёт о спецтехнике находящейся в ремонте Maks 20.04.2026 Отчёт из решения ниже размещен в конфигурации КА2. Задача: отобразить спецтехнику, которая на данный момент находится в ремонте. Есть нетиповой документ "Заявка на ремонт спецтехники" который. . .	Памятка для бота и "визитка" для читателей "Semantic Universe Layer (Слой семантической вселенной)" Hrethgir 19.04.2026 Сгенерировано для краткого описания по случаю сборки и компиляции скелета серверного приложения. И пусть после этого скажут, что статьи сгенерированные AI - туфта и не интересно. И это не реклама -. . .

@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