Живые точки

@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
Заранее спасибо за помощь

@yaneumniy · 14.01.2020, 23:48

не подскажешь как решить задачу?

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

я скинул уже код

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

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]))

Добавлено через 1 минуту
Ребят можете отправить "спасибо" буду благодарен

@yaneumniy · 14.01.2020, 23:56

жаль пробелов нет
не мог бы мне помочь?

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

мдамс, даже пробелы не расставить без помощи. У меня просто только телефон под рукой

@Manwithoutname · 15.01.2020, 00:03

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

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

Эх, где ж ты был все это время

А вообще, можешь нормально вставить код? хочу поэкспериментировать

@mlsdmitry · 15.01.2020, 00:07 **[ТС]**

Я писал чел

попробую нормально:/ но на телефонето ад

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

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]))

Добавлено через 1 минуту
Ты сортировал один массив, я его разрезал на два. И ещё потом на 3, не проверял быстрее ли, но должно быть. Ибо здесь сортировка гораздо меньше.

@Manwithoutname · 15.01.2020, 00:10

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

Я писал чел попробую нормально:/ но на телефонето ад

Не могу понять, как ты вообще не решил это. Судя по сообщениям и незнакомым странным словам, ты очень даже шаришь за программирование и код, по сравнению с такими имбецилами, как я. Теперь будем вместе в конце топа плестись :/

@mlsdmitry · 15.01.2020, 00:12 **[ТС]**

Да честно говоря не страшно, я бы не сказал что шарю просто уделяю все время-_-
Кстати есть телеграмм?

@Manwithoutname · 15.01.2020, 00:15

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

Да честно говоря не страшно, я бы не сказал что шарю просто уделяю все время-_-
Кстати есть телеграмм?

Конешн) "Не шарю, просто уделяю все свободное время"... Эх, хорошо быть молодым. А у нас, старичков, свободного времени просто нет :| и да... С КАКИХ ПОР ЭТО НЕ ШАРЮ?!

@mlsdmitry · 15.01.2020, 00:34 **[ТС]**

Давай лучше не на форуме, у меня просто вопросы есть. Но по правилам здесь нельзя.

Добавлено через 18 секунд
Manwithoutname, https://t.me/mlsDmitry

Новые блоги и статьи Все статьи Все блоги /
Генератор паролей (вариант №4) Maks 01.11.2026 После публикации 3-го варианта генератора паролей, разослал его своим коллегам (с целью оценки), в итоге были получены следующие рекомендации: 1. Вернуть возможность использования знаков \| 1 l I;. . .	Генератор паролей (вариант №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. Скачиваем с. . .

@yaneumniy 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 4
	14.01.2020, 23:48
	не подскажешь как решить задачу? 0

@yaneumniy 0 / 0 / 0 Регистрация: 14.01.2020 Сообщений: 4
	14.01.2020, 23:56
	жаль пробелов нет не мог бы мне помочь? 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	14.01.2020, 23:58 [ТС]
	мдамс, даже пробелы не расставить без помощи. У меня просто только телефон под рукой 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	15.01.2020, 00:12 [ТС]
	Да честно говоря не страшно, я бы не сказал что шарю просто уделяю все время-_- Кстати есть телеграмм? 0

@mlsdmitry 3 / 3 / 1 Регистрация: 11.01.2020 Сообщений: 22
	15.01.2020, 00:34 [ТС]
	Давай лучше не на форуме, у меня просто вопросы есть. Но по правилам здесь нельзя. Добавлено через 18 секунд Manwithoutname, https://t.me/mlsDmitry 0

Живые точки

Решение