Живые точки

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

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

Новые блоги и статьи Все статьи Все блоги /
10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .	сукцессия 9. Математика подлости: как растения предали грибных друзей anaschu 27.06.2026 Статья 2. Глобальная фосфорная война: эволюционно-экономические механизмы распределения биомов Земли Введение: Экологический рынок как игра с нулевой суммой Традиционная экология долгое время. . .	сукцессия 8. Как я спорил с ИИ, которые - агенты растений и ненавистники грибов! anaschu 27.06.2026 Статья 1. Хроники грибного восстания: как Сократов диалог разрушил академические догмы ИИ Введение: Синдром «цифрового учебника» Современные большие языковые модели (LLM) обладают колоссальным. . .	Главный вопрос моделирования сукцессии anaschu 27.06.2026 главный вопрос. Если эктомикориза лучше добывает недоступный фосфор. И ее масса максимальна из всех. А широколиственный лес тоже имеет самую крутую биомассу. То почему не возникло их симбиоза? Это. . .
сукцессия 6. Питон реализация энилоджиковской модели, картинка про Центральную часть будущей модели anaschu 26.06.2026 Етить. ИИ мне на основе моего старого файла R создал вот эту вот хмерь на пайтоне. Это уже новая модель, модель сукцессии грибной. потоки фосфора, азота. Углерода. 5 видов организмов. Я даже. . .	Как замкнутый ядерный цикл решит проблему недостатки фосфора? Био миграция фосфора со дна океана anaschu 26.06.2026 Биологический лифт: Концепция подъема фосфора со дна океана с помощью ЗЯТЦ Предлагаю на обсуждение альтернативу тяжелому промышленному бурению океанического дна. Вместо сложной инженерии мы можем. . .	сукцессия 5 anaschu 26.06.2026 ПЛАН РАЗРАБОТКИ математической модели сукцессии микоризных систем Переход AM → EcM (Endo + ErM) · Шумилов А. С. · ИФХиБПП РАН · Пущино · 2026 . . .	сукцессия 4 anaschu 25.06.2026 Более детализированный план разработки План доработки модели динамики микоризных симбиозов (EcM с гистерезисом) Цель: Реализовать логику переключения между эрикоидным (ErM) и эктомикоризным. . .

@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