Живые точки

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

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

Новые блоги и статьи Все статьи Все блоги /
Вангую, что это не пройдёт модерацию, и на неделе я запущу свой сервер. 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-мерного ОДУ-моделирования вековой сукцессии (ветка. . .	Текстовый слайдер с нумерацией страниц и кроссбраузерность. russiannick 18.07.2026 Один мой друг написал текстовый слайдер с нумерацией страниц. Сегодня я расскажу как он умудрился подружить его с кроссбраузерностью. Очевидно сложно угодить с шириной каждому браузеру. Один крадет. . .	Грибы - это мемы, дерево - это человек. Применение микоризной модели к теории меметики Докинза. anaschu 18.07.2026 Меметический изоморфизм теории «всего»: Грибная сукцессия как модель эволюции идей Докинза Базовый код системы ОДУ микоризной сукцессии описывает не просто биологию, а универсальную. . .

@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