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

@Misha2005 · Регистрация: 25.06.2020

Студворк — интернет-сервис помощи студентам

Разделение королевства
Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся 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

@u235 · 18.08.2021, 21:01

Gdez, думаю что отличие в алгоритмической сложности sorted и min..

@Gdez · 18.08.2021, 21:59

u235, согласен: мой код медленнее. Но я про решение через множества...

@Fscoder · 19.08.2021, 14:04

Если что, вот еще вариант, который прошел на сириусе. Проблема быстродействия магическим образом решилась кортежем. Жду объяснения этому от здешних светлых умов

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
34
n = int(input())
 
arr_xy = []
 
ans_x = set()
ans_y = set()
 
for i in range (n):
 
    x,y = map(int,input().split())
 
    arr_xy.append ((x,y))
 
arr_xy.sort()
 
for i in range (n - 1):
 
    if (arr_xy[i + 1][0] == arr_xy[i][0]) and (arr_xy[i + 1][1] > arr_xy[i][1]):
 
        ans_y.add(arr_xy[i][1] + 1)
 
    else:
 
        ans_x.add(arr_xy[i][0] + 1)
 
print (len(ans_x) + len(ans_y))
 
for i in ans_y:
 
    print ("y", i)
 
for i in ans_x:
 
    print ("x", i)

@Gere · 19.08.2021, 17:09

не подходит по временни

@Tosoh · 19.08.2021, 23:35

ваша программа выдает неверный ответ

@koipaqwe · 20.08.2021, 15:35

помогите пожалуйста решить

@SOME_ONE_IN_DAY · 12.10.2021, 10:43

Евгений, не проходит по времени, я проверил.

@Crazy lancaster · 12.10.2021, 14:46

блин, вот из-за таких штук реально горит с этого сириуса, причём неоднократно

Новые блоги и статьи Все статьи Все блоги /
Особенности gif сгенерированных в Си russiannick 21.10.2026 Рассмотрим генерацию gif файлов, которые в Си имеют свои особенности. Gif представляет собой графический формат популярный в интернете. Посмотрим на палитру. Gif файл сгенерированный в си отличается. . .	FPS контроллер с анимированными Y-Bot и 3D-звуком miniaudio (Box3D, Recast, BehaviorTree.CPP, ozz-animation, ImGui, OpenGL и SDL3) 8Observer8 18.10.2026 Содержание блога \| English Version Полное мультиплатформенное руководство по стартовому проекту с FPS-контроллером игрока, анимированными роботами Y-Bot с 4-слойным блендингом, 3D-физикой Box3D,. . .	Локальный http сервер Argus19 17.10.2026 Локальный http сервер На работе, на двух локальных компьютерах круглосуточно работают программы опроса приборов с записью в книги Excel,которые раз в сутки записываются на сервер компании. Т. к. . . .	Копировать Windows на новый диск на UEFI damix 17.10.2026 https:/ / uriesk. wordpress. com/ 2016/ 11/ 01/ move-window-10-to-ssd-on-a-uefi-dualboot-system-with-basic-linux-tools/ TL DR Вставляем диск, а старый подключаем через переходник, грузимся с лайва. . .
ИИ не может найти нужный язык в списке Supersumestria 05.10.2026 Я ему даю вот такое изображение и прошу найти и подчеркнуть немецкий язык. Возвращает он вот это: https:/ / i. **********/ vqBWLe2. png Нужную строчку в 3й колонке просто выдумал. . Это. . .	Новая последняя моя музыка в SUNO zorxor 05.10.2026 Здравствуйте, дорогие мои друзья! С большой радостью я хотел бы представить вам свою новую последнею музыку, которую сгенерировала мне по моей просьбе нейросеть SUNO. С уважением, zorxor. Это. . .	Программный домашний кинотеатр russiannick 27.09.2026 Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .	Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого zorxor 21.09.2026 Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .

@Misha2005 3 / 3 / 0 Регистрация: 25.06.2020 Сообщений: 11

	Разделение королевства 25.06.2020, 13:22. Показов 30523. Ответов 27 Метки python 3.7 (Все метки) Разделение королевства Королевство Флатландия имеет вид бесконечной двумерной плоскости. В королевстве находятся 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

@u235 5535 / 2888 / 573 Регистрация: 07.11.2019 Сообщений: 4,814
	18.08.2021, 21:01
	Gdez, думаю что отличие в алгоритмической сложности sorted и min.. 0

@Gdez 8851 / 4502 / 1864 Регистрация: 27.03.2020 Сообщений: 7,320
	18.08.2021, 21:59
	u235, согласен: мой код медленнее. Но я про решение через множества... 0

@Gere 0 / 0 / 0 Регистрация: 19.08.2021 Сообщений: 1
	19.08.2021, 17:09
	не подходит по временни 0

@Tosoh 0 / 0 / 0 Регистрация: 07.08.2021 Сообщений: 5
	19.08.2021, 23:35
	ваша программа выдает неверный ответ 0

@koipaqwe 1 / 1 / 0 Регистрация: 10.07.2021 Сообщений: 27
	20.08.2021, 15:35
	помогите пожалуйста решить 0

@SOME_ONE_IN_DAY 0 / 0 / 0 Регистрация: 10.10.2021 Сообщений: 1
	12.10.2021, 10:43
	Евгений, не проходит по времени, я проверил. 0

@Crazy lancaster 0 / 0 / 0 Регистрация: 29.09.2021 Сообщений: 1
	12.10.2021, 14:46
	блин, вот из-за таких штук реально горит с этого сириуса, причём неоднократно 0