Живые точки

@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, 22:05

хех) и как? смог на 10 уже?

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

Неа

@Manwithoutname · 14.01.2020, 22:07

И да, не помогло, сделал как-то так. По ощущениям в пайчарме ответ выдает быстрее точно, но в ответе то же самое время. Такое чувство, что у них что-то с серверами.

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:
    kxcoor = []
    px, py = coor[i][0], coor[i][1]
    for j in coor:
        if j[1] == py and j[0] != px:
            kxcoor.append([0, j[0], abs(j[0] - px)])
        elif j[0] == px and j[1] != py:
            kxcoor.append([1, j[1], abs(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]))

Добавлено через 45 секунд
Теперь ваша очередь пробовать, а то у меня ток 2 попытки осталось, а впереди еще полтора часа

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

Ладно, я сейчас скопирую потестю с timeit скажу где у тебя хромает

@pskobx · 14.01.2020, 22:08

думаю что с серверами все норм.. а ощущения в пайчарме это не особо показатель, думаю)

@Manwithoutname · 14.01.2020, 22:12

Я - самая быстрая рука на всём Диком Западе, так что я верю своим ощущением) а по поводу сервов, то приведу просто пример. Я один и тот же код три раза кидал, а результатами по времени было это: 1 - 1060ms, 2 - 1030ms, 3 - 1090ms. А дальше ток 1090 и держится. Один и тот же код, но такая разница. Что-то не так... Или я накручиваю себя

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

ща покажу, если я прав

@Manwithoutname · 14.01.2020, 22:12

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

Ладно, я сейчас скопирую потестю с timeit скажу где у тебя хромает

Я не знаю, что это, но желаю удачи) (да-да, я оладушек, смиритесь)

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

px, py = coor[i] сделай так, сейчас еще найду

Добавлено через 2 минуты
x, y = j
if y == py and x != px:
kxcoor.append([0, x, abs(x - px)])
elif x == px and y != py:
kxcoor.append([1, y, abs(y - py)])

это вообще время сокращает

Добавлено через 1 минуту
8.988380432128906e-05 это было
7.510185241699219e-05 стало

@Manwithoutname · 14.01.2020, 22:35

Спс, но пока что не буду пробовать и еще подожду ваших идей) а то так все попытки истрачу

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

да често говоря у тебя сортировка 2.~ и return 2~ так что тут либо переписывать либо смириться

@Manwithoutname · 14.01.2020, 22:39

Есть идеи тогда? А то я как вижу, ты обладаешь неплохими знаниями, а все еще не решил.

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

лол, чел у тебя задача на моих тестах не работает -_-
5
1 2
3 2
5 2
3 0
3 4
2 3 5
3 5
выводит 12 надо 60

@Manwithoutname · 14.01.2020, 22:45

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

лол, чел у тебя задача на моих тестах не работает -_-

все проходит :0

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

а нет сори, все ок

@Manwithoutname · 14.01.2020, 22:54

8.9 также, да?

@yaneumniy · 14.01.2020, 23:24

ты как в итоге сделал?
я делал через отдельную функцию, и словари 8,9 ошибка по времени
пытался этот код в словари запихнуть, и ничего не вышло

@Manwithoutname · 14.01.2020, 23:26

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

ты как в итоге сделал?
я делал через отдельную функцию, и словари 8,9 ошибка по времени
пытался этот код в словари запихнуть, и ничего не вышло

У меня также 8.9. Знакомый из группы сделал на 10 с помощью словарей, я тож почти сделал, но уже не успею к дедлайну(
Приятного и всем удачи :3

@yaneumniy · 14.01.2020, 23:34

не я конечно всё понимаю, но этого не понимаю
не подскажешь как сделать задачу?

@mlsdmitry · 14.01.2020, 23:47 **[ТС]**

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
n = int(input())
points = []
for _ in range(n):
    points.append([int(i) for i in input().split()])
moves = [int(i) - 1 for i in input().split()]
for i in moves:
    found_points_v = []
    found_points_h = []
    found_points = []
    px, py = points[i]
    for j in points:
        x, y = j
        if y == py and x != px:
            found_points_h.append([0, x, abs(x - px)])
        elif x == px and y != py:
            found_points_v.append([1, y, abs(y - py)])
    if found_points_v:
        found_points_v.sort(key=lambda q: (q[2], -q[1], -q[0]))
        found_points.append(found_points_v[-1])
    if found_points_h:
        found_points_h.sort(key=lambda q: (q[2], -q[1], -q[0]))
        found_points.append(found_points_h[-1])
    found_points.sort(key=lambda q: (q[2], -q[1], -q[0]))
 
    if found_points:
        w = found_points[-1]
        if w[1] <= points[i][w[0]]:
            points[i][w[0]] = w[1] - w[2]
        else:
            points[i][w[0]] = w[1] + w[2]
xy = input().split()
x, y = int(xy[0]), int(xy[1])
print(abs(points[x - 1][0] - points[y - 1][0]) * abs(points[x - 1][1] - points[y - 1][1]))

я не успел сдать, но это гораздо ускоренее

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №3) Maks 30.10.2026 Финальная версия генератора паролей 1С. Доработка решения в этот раз коснулась только визуальной части, а именно, добавлен реквизит ДопПараметры (тип Булево), который скрывает/ отображает реквизиты:. . .	Магическое мышление и магия, современная наука не отличима от магии (говорит ИИ Джемени) zorxor 30.10.2026 Джемени, расскажи, пожалуйста, что такое магическое мышление, что такое магия, почему современная наука чем-то напоминает магию? Фраза «Любая достаточно развитая технология неотличима от магии». . .	За какое время ИИ может подобрать пароль по хешу (рассказывает Джемени ИИ) zorxor 30.10.2026 Расскажи, Джемени, если известен хэш МД5, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .	Кто убил 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 Реализация из решения ниже выполнена в самописной конфигурации на БСП (помощь начинающему коллеге). Задача: Программно добавить префикс в нумерацию документов. Решение: В модуле объекта. . .

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 22:05
	хех) и как? смог на 10 уже? 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:05 [ТС]
	Неа 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:08 [ТС]
	Ладно, я сейчас скопирую потестю с timeit скажу где у тебя хромает 0

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

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 22:12
	Я - самая быстрая рука на всём Диком Западе, так что я верю своим ощущением) а по поводу сервов, то приведу просто пример. Я один и тот же код три раза кидал, а результатами по времени было это: 1 - 1060ms, 2 - 1030ms, 3 - 1090ms. А дальше ток 1090 и держится. Один и тот же код, но такая разница. Что-то не так... Или я накручиваю себя 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:12 [ТС]
	ща покажу, если я прав 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:27 [ТС]
	px, py = coor[i] сделай так, сейчас еще найду Добавлено через 2 минуты x, y = j if y == py and x != px: kxcoor.append([0, x, abs(x - px)]) elif x == px and y != py: kxcoor.append([1, y, abs(y - py)]) это вообще время сокращает Добавлено через 1 минуту 8.988380432128906e-05 это было 7.510185241699219e-05 стало 0

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 22:35
	Спс, но пока что не буду пробовать и еще подожду ваших идей) а то так все попытки истрачу 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:38 [ТС]
	да често говоря у тебя сортировка 2.~ и return 2~ так что тут либо переписывать либо смириться 0

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 22:39
	Есть идеи тогда? А то я как вижу, ты обладаешь неплохими знаниями, а все еще не решил. 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:42 [ТС]
	лол, чел у тебя задача на моих тестах не работает -_- 5 1 2 3 2 5 2 3 0 3 4 2 3 5 3 5 выводит 12 надо 60 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 22:46 [ТС]
	а нет сори, все ок 0

@Manwithoutname 0 / 0 / 0 Регистрация: 05.12.2019 Сообщений: 28
	14.01.2020, 22:54
	8.9 также, да? 0

@yaneumniy 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 4
	14.01.2020, 23:24
	ты как в итоге сделал? я делал через отдельную функцию, и словари 8,9 ошибка по времени пытался этот код в словари запихнуть, и ничего не вышло 0

@yaneumniy 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 4
	14.01.2020, 23:34
	не я конечно всё понимаю, но этого не понимаю не подскажешь как сделать задачу? Миниатюры 0