Живые точки

@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

Новые блоги и статьи Все статьи Все блоги /
Проверка полного ФИО в типовом справочнике Maks 07.11.2026 Решение реализовано в конфигурации КА2, на примере справочника "КонтактныеЛицаПартнеров". Задача: Запрет инициалов. Не допускаеть использование сокращений вида "И. И. ", "И. И. ", "И И" и. . .	Про "Windows must die!" kumehtar 04.11.2026 Знаете, чет накатило. . . . Когда-то это было почти боевым кличем: мол, нормальный человек сидит на DOS, OS/ 2 или Linux, а вот это вот - Must Die. А теперь человек произносит «мастдай» с усмешкой - и. . .	Красочные поля с номером страницы svg+background-image russiannick 04.11.2026 Красочные поля с номером страницы не менее важны чем в эпоху бумажных книг. Посему спешу представить почтеннейшей публике этот важный инструмент который эти поля и формирует. В процессе разработки. . .	Вступаем в новую фазу генерации favicons, векторную. russiannick 02.11.2026 Теперь нет нужды скрывать что используется простой svg. Исходный код изображения помещаем в поле и жмем кнопку. Исходник преобразуется в вид корректный для помещения в favicon или в url(). Нажатие. . .
Генератор паролей (вариант №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, например, за сколько ИИ сможет подобрать соответствующий пароль? Искусственный интеллект (ИИ) может подобрать простой или средний по сложности пароль по. . .

@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

Живые точки

Решение