Форум программистов, компьютерный форум, киберфорум
Python для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск Заказать работу  
 
 
Рейтинг 4.77/124: Рейтинг темы: голосов - 124, средняя оценка - 4.77
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11

Разделение королевства

25.06.2020, 13:22. Показов 29673. Ответов 27

Студворк — интернет-сервис помощи студентам
Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более удобного составления карт в Флатландии была введена Декартова система координат. Известно, что i-й замок находится в точке с координатами (xi+0.5, yi+0.5), где xi, yi — целые числа. Местоположения всех замков попарно различны.

На старости лет король решил разделить на карте королевство между своими сыновьями прямыми, параллельными осям координат. Если прямая параллельна оси Ox, то y координата у всех точек на прямой должна быть целым числом, иначе x координата у всех точек должна быть целым числом. В обоих случаях соответствующие целые координаты по модулю не должны превышать 2⋅109. При этом Его величество хочет, что бы после разделения королевства любые два замка оказались бы в различных частях.

Помогите королю разделить королевство, используя не более чем n−1 прямых. У любой пары прямых должно быть не более одной общей точки.

Входные данные

В первой строке задано целое число n (1≤n≤100000) — количество замков в королевстве. В следующих n строках записано по два числа xi и yi (−109≤xi≤109, −109≤yi≤109) — целые части координат замков.

Выходные данные

В первой строке выходного файла выведите количество используемых прямых. В следующих строчках выведите сами прямые, по одной в каждой строке. Если прямая параллельна оси Ox, то выведите символ "y", а затем через пробел y координату всех точек на этой прямой, иначе выведите символ "x", а затем через пробел x координату всех точек на этой прямой.



Примеры
Ввод
Вывод
4
0 2
0 3
1 2
1 3
2
y 3
x 1
0
cpp_developer
Эксперт
20123 / 5690 / 1417
Регистрация: 09.04.2010
Сообщений: 22,546
Блог
25.06.2020, 13:22
Ответы с готовыми решениями:

Разделение королевства. Встроенные структуры данных
Разделение королевства Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более...

Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более удобного составления карт в...

Разделение Королевства
Разделение королевства Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более...

27
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
25.06.2020, 14:05  [ТС]
Вот примерный порядок решения, но я не знаю как его реализовать:
1.Отсортируем замки по координате x, между каждой парой соседних замков проведем прямую
2.Посмотрим на замки, которые имеют одинаковую координату x. Для каждого такого замка отсортируем по y. Проведем прямую между соседними замками
1
Status 418
Эксперт Python
4584 / 2350 / 601
Регистрация: 26.11.2017
Сообщений: 5,262
Записей в блоге: 3
25.06.2020, 14:24
ввод и сортировка так:
Python
1
2
3
4
5
6
7
n = int(input())
a = []
for _ in range(n):
    x, y = map(int, input().split())
    a.append((x, y))
a.sort()
print(*a)
1
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
25.06.2020, 16:44  [ТС]
А как делать дальше?
1
3 / 3 / 0
Регистрация: 25.06.2020
Сообщений: 11
25.06.2020, 18:17  [ТС]
Программа работает нормально, но не проходит по времени:

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())
 
a = list()
b = list()
x = set()
y = set()
for i in range(n):
    xx, yy = map(int, input().split())
    a.append([xx, yy])
    b.append([yy, xx])
a.sort()
b.sort()
for i in range (n - 1):
    if a[i+1][0] == a[i][0] and a[i+1][1] > a[i][1]:
        y.add(a[i][1] + 1)
    else:
        x.add(a[i][0] + 1)
print(len(x) + len(y))
for i in y:
    print("y " + str(i))
for i in x:
    print("x " + str(i))
Добавлено через 28 минут
Уже решил
0
0 / 0 / 0
Регистрация: 26.06.2020
Сообщений: 1
26.06.2020, 18:32
Ну что зашла задача?
0
1 / 1 / 0
Регистрация: 26.06.2020
Сообщений: 30
26.06.2020, 19:11
Можешь код отправить, пожалуйста
0
25 / 14 / 2
Регистрация: 28.06.2020
Сообщений: 50
28.06.2020, 01:38
Код данный ранее работает, просто там ведется лишний список b, который и замедляет программу.
1
1 / 1 / 0
Регистрация: 26.06.2020
Сообщений: 30
28.06.2020, 12:59
Я убирал список b, все равно медленно

Добавлено через 12 минут
Все, решил
0
8 / 7 / 1
Регистрация: 15.05.2020
Сообщений: 10
30.06.2020, 15:25
Я тоже убрал список, но все равно медленно работает, что нужно еще сделать?
0
11 / 15 / 1
Регистрация: 13.05.2020
Сообщений: 49
30.06.2020, 19:34
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
n = int(input())
a = list()
x = set()
y = set()
for i in range(n):
    xx, yy = map(int, input().split())
    a.append([xx, yy])
a.sort()
for i in range(n - 1):
    if a[i + 1][0] == a[i][0] and a[i + 1][1] > a[i][1]:
        y.add(a[i][1] + 1)
    else:
        x.add(a[i][0] + 1)
print(len(x) + len(y))
for i in y:
    print("y " + str(i))
for i in x:
    print("x " + str(i))
2
6 / 5 / 1
Регистрация: 25.05.2020
Сообщений: 17
30.06.2020, 22:55
По времени не пройдёт
0
11 / 15 / 1
Регистрация: 13.05.2020
Сообщений: 49
01.07.2020, 09:34
AndreyNill, У меня прошло.
ниже скрины.
Миниатюры
Разделение королевства   Разделение королевства   Разделение королевства  

Разделение королевства  
1
1 / 1 / 0
Регистрация: 07.03.2020
Сообщений: 15
10.07.2020, 11:46
Евгений, не проходит по времени, я проверил.

Добавлено через 9 минут
Я не понимаю как и почему, но можно добавить пробел в конец кода и тогда заработает. Я не знаю как, но у меня зачиталось. Приношу извинения за то, что сказал неправду в сообщении выше.
0
2 / 2 / 0
Регистрация: 11.07.2021
Сообщений: 2
11.07.2021, 23:52
AndreyNill, у меня тоже в сириусе ,по времени не проходит. .
2
0 / 0 / 0
Регистрация: 27.07.2021
Сообщений: 1
29.07.2021, 11:45
у меня ничего не получается(((((( на всех попытках -- сваливается на времени
0
1 / 1 / 0
Регистрация: 11.10.2020
Сообщений: 2
18.08.2021, 12:53
Актуально
0
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,317
18.08.2021, 16:16
Лол123, вроде так
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
xs, ys, xx, yy = set(), set(), set(), set()
 
n = int(input())
 
for i in range(n):
    x, y = map(int, input().split())
    
    if y in xs:
        xx.add(y)
    else:
        xs.add(y)
        
    if x in ys:
        yy.add(x)
    else:
        ys.add(x)
 
print(len(xx) + len(yy) - 2)
 
for i in sorted(yy)[1:]:
    print('x',i)
for i in sorted(xx)[1:]:
    print('y',i)
0
5517 / 2870 / 571
Регистрация: 07.11.2019
Сообщений: 4,761
18.08.2021, 18:42
Gdez, вы думаете что нужна сортировка?
Вариант:
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
xx, yy = set(), set()
n = int(input())
for i in range(n):
    x, y = map(int, input().split())
    xx.add(x)
    yy.add(y)
xx.remove(min(xx))
yy.remove(min(yy))
print(len(xx) + len(yy))
for i in yy:
    print('y',i)
for i in xx:
    print('x',i)
1
Эксперт Python
8851 / 4502 / 1864
Регистрация: 27.03.2020
Сообщений: 7,317
18.08.2021, 19:18
u235, полтора года назад была нужна - сириус...
Верхний вариант (пробовал найти минимум прямых) не верен.
А так
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
x, y = set(), set()
 
n = int(input())
 
for i in range(n):
    for w,s in zip(map(int, input().split()),(x,y)):
        s.add(w)
 
print(len(x) + len(y) - 2)
 
for i in sorted(x)[1:]:
    print('x',i)
for i in sorted(y)[1:]:
    print('y',i)
Что, впрочем, аналогичен Вашему
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
raxper
Эксперт
30234 / 6612 / 1498
Регистрация: 28.12.2010
Сообщений: 21,154
Блог
18.08.2021, 19:18
Помогаю со студенческими работами здесь

Разделение королевства
Разделение королевства Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся n замков. Для более...

Столица королевства
В некотором царстве, в некотором государстве было S городов, и все они, судя по главной карте императора, имели целые координаты. В те годы...

Задание про 2 королевства
Алиса и Боб стали королями в королевствах на множестве натуральных чисел. Подданными Алисы являются все натуральные числа, которые делятся...

Задача про раздел королевства
Король решил разделить королевство между двумя своими сыновьями. При этом он хочет минимизировать будущие расходы на административное...

Посчитать минимальные расходы королевства на подарок короля
В Берляндии наступил праздник равенства. В честь праздника король решил за счёт государственной казны уравнять благосостояние всех граждан...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Новые блоги и статьи
модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий
anaschu 08.04.2026
https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI
Блокировка документа от изменений, если он открыт у другого пользователя
Maks 08.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .
Система безопасности+живучести для сервера-слоя интернета (сети). Двойная привязка.
Hrethgir 08.04.2026
Далее были размышления о системе безопасности. Сообщения с наклонным текстом - мои. А как нам будет можно проверить, что ссылка наша, а не подделана хулиганами, которая выбросит на другую ветку и. . .
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов.
anaschu 08.04.2026
работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ
Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики.
Hrethgir 07.04.2026
Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .
Горе от ума
kumehtar 07.04.2026
Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .
Использование значений реквизитов справочника в документе, с определенными условиями и правами
Maks 07.04.2026
1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию
Maks 07.04.2026
Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru