Задача "Столица"

В некотором царстве, в некотором государстве было N городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|. Император решил построить N+1-ый город и сделать его столицей своего государства, при этом координаты столицы также должны быть целыми. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города. Нелегкая задача выбрать место для столицы поручена Вам.

Ввод
Первая строка содержит число N (1 ≤ N ≤ 100). Следующие N строк содержат координаты городов - пары целых чисел, не превышающих 1000 по абсолютной величине.
Вывод
Выведите два целых числа - координаты точки, где следует построить столицу. Если решений несколько, выведите любое.

Ввод
4
0 0
1 1
0 1
1 0
Вывод
0 -1
,
Можете написать программу на с++ или хотя бы алгоритм показать как надо решить?

0

Сообщение от devcpp чтобы среднее арифметическое расстояний между

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

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

Сообщение от devcpp столицу нельзя строить на месте существующего города.

Если бы не это условие, то задача совсем проста. Просто берем медианную координату по x - xM, по y - yM, и строим столицу в точке (xM, yM). Это для нечетного количества городов. В четном случае у нас получается квадрат (возможно, вырожденный) из самых близких к медианным значениям.
Поясню, что я имею в виду под "медианой". Для ряда 0 3 4 25 100 1000 1001 медианой будет 25
Для ряда 0 3 4 25 100 1000 1001 2000 "медианными" значениями будут 25 100. В первом случае столицу нужно строить в точке 25. Во втором - в любой точке 25 <= x < 100. Аналогично по координате Y.
Но в данном случае дело осложняется тем, что "хорошие" точки уже могут быть заняты существующими городами. Тогда, наверное, подойдет любая ближайшая (в смысле заданной метрики) незанятая точка.

1

devcpp
Вам надо найти минимум функции
|x - x1| + |x - x2| + ... + |x - xN| + |y - y1| + |y - y2| + ... + |y - yN|
поскольку |x| <= 1000 и |y| <= 1000 , то простой перебор
решит эту задачу. Дополнительно вам нужно задать
два массива содержащие координаты x1, x2,....y1, y2, ...
Эти массивы нужны также, чтобы пропустить координаты
существующих городов.
...
Меня заинтересовала эта задача. Пожалуй её можно решить
быстрее. Как? Надо сделать два перебора. Отдельно по икс и
Отдельно по игрек. Две минимальные величины и дадут
координаты столицы.

0

Сообщение от echs Надо сделать два перебора

Да не надо никаких переборов! Лишняя трата своего и машинного времени. Просто берете середину, вот и все.
Смотрите. Пусть есть ряд 1 20 100. В точке 20 сумма расстояний = 99 А в точке 21 - 100. При сдвиге направо от любой точки расстояние до точек расположенных левее увеличивается. До точек расположенных правее уменьшается на то же дельта (до каждой) Вот и вся высшая математика.

1

Славный Байт,
Вы меня извините, но что вы подразумеваете под СЕРЕДИНОЙ?
Элементы статистики тут не пройдут. Города могут быть в одной
куче (или в двух) где-нибудь с краю. Вы мне друг, но истина тоже
мой друг. Давайте жить дружно.
Может я ошибаюсь. Вы не могли бы на примере трёх городов
указать на мои ошибки? Буду очень вам благодарен.

0

Сообщение от echs Вы не могли бы на примере трёх городов

Зачем же так себя ограничивать? Мы города не экономим, все равно они не наши. Только можно в одномерном случае? На двумерный вы сами легко обобщите.
Вот координаты городов
1 2 4 5 10 40 50 100
Столицу надо строить между городами 5 и 10. И нигде больше.
Попробуйте ее сместить в точку 3 посмотрите, что получится (хоть там и сгущение)
Вообще, поставьте столицу в любую точку. И посмотрите, что происходит с расстояниями, как они изменяются при ее смещении на 1 км влево или вправо. И что происходит при перепрыгивании через какой-то город.
А вот нечетная ситуация 1 3 25. Если бы не ограничение (тоже мне, Петр Первый нашелся!) столицей должен стать город в точке 3. Но поскольку мы не можем идти против воли Его Величества, то строить будем на 2-м или 4-м километре (без разницы)

Добавлено через 5 минут
Может быть вас лучше убедит (и проще считать) крайний случай - 2 города. Так вот тут столицу можно строить в любом месте отрезка их соединяющего. Сумма расстояний все равно будет равной длине отрезка.
А для двумерного случая - в любой точке прямоугольника (включая границы), противоположными вершинами которого будут эти города.
Не поленитесь, нарисуйте картинку, посчитайте отрезки...

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

1

Сообщение от Байт Зачем же так себя ограничивать? Мы города не экономим, все равно они не наши. Только можно в одномерном случае? На двумерный вы сами легко обобщите. Вот координаты городов 1 2 4 5 10 40 50 100 Столицу надо строить между городами 5 и 10. И нигде больше.

Примеры какие-то подтасованные и все равно непонятно, о какой "середине" идет речь.

У нас может быть много городов на одном краю диапазона и один единственный город на другом. Пусть у нас есть 900 городов с координатой 0 и один город с координатой 1000. Понятно, что оптимальная точка для столицы при этом будет точкой с координатой 1.

И где тут "середина"?

Понятно, что в общем случае нас интересует центр масс, а не какая-то "середина". Но в данном случае - в метрике L₁. В этой метрике двумерная задача действительно распадается на две одномерные. То есть просто усредняем каждую координату по отдельности и, если место занято, ищем ближайшее свободное место.

0

Сообщение от TheCalligrapher И где тут "середина"?

Средина - по количеству. Чтобы слева и справа было одинаковое число городов.

1

Сообщение от TheCalligrapher И где тут "середина"?

Уважаемый Shamil1 вам ответил. Этого недостаточно?

Сообщение от TheCalligrapher нас интересует центр масс,

При чем тут массы?

Сообщение от TheCalligrapher Примеры какие-то подтасованные

Да возьмите любой пример, который вам в голову придет. И посмотрите. Можете даже программку простую составить. При нечетном количестве оптимальной будет средняя точка. При четном - любая точку между двумя средними.
Все так просто, что даже смешно.

0

Байт,

Сообщение от Байт Столицу надо строить между городами 5 и 10. И нигде больше.

почему именно там а не на 4 40

0

Сообщение от devcpp почему именно там а не на 4 40

А вы попробуйте, как говаривал полковник Най-Турс. Просто поместите столицу в любом другом месте, и посчитайте сумму расстояний. А потом подвигайте ее. +1, -1... И посмотрите, что с этими расстояниями происходит, как изменяется каждое...

Добавлено через 1 час 15 минут
Друзья! Я должен признаться, что по этой задаче у меня есть некоторая фора перед вами. Дело в том, что когда я был еще в щенячьем возрасте и озаботился трудоустройством, в одном из знакомых институтов возникла подобная задача. Что-то типа размещения главного телефонного узла в здании больницы (Вай-Фая тогда еще не было). И зная меня, как подающего надежды программиста (а я, конечно, обещал все сделать в лучшем виде, и кой-какие соображения насчет переборов у меня были), пригласили в это НИИ, даже не взирая на некоторые отягчающие обстоятельства типа 5-го пункта. И вот, ожидая приема в отделе кадров, я что-то чиркал на листочке, искал оптимальности, дошел чуть ли но "ветвей и границ". И вдруг - все увидел!
Кадровичка была смущена моим безумным глазом. "вот, еще одного психа принесло в наш дружный коллектив!". Но все обошлося.
Мне б, дураку, сделать надменный вид, мол пишу очень сложную программу... А я с места в карьер все начальничкам и рассказал. Типа, задачка-то - школьная. стройте вашу станцию в этом квадрате (кубе) и показал как эта вся "оптимизация" получается. И как бы оказался не у дел.
Но ничего, опять обошлось. Подвалили потихонечку другие задачки... Не подвел я коллектив

0

Суть этой задачи не в нахождении идеального места для столицы, а в нахождении наилучшего свободного места.

Мы считываем координаты всех городов в некоторую структуру данных, одновременно вычисляя "идеальный квадрат" (любая или обе стороны квадрата могут быть вырождены). Если идеальные места заняты, то нам нужно быстро отвечать на вопросы типа "сколько городов на данной горизонтали/вертикали" и "есть ли город в данной точке".

0

Сообщение от Shamil1 а в нахождении наилучшего свободного места.

Дык, особых сложностей не вижу. Если квадрат занят, так берем ближайшие пустые места (в смысле заданной метрики) простым обходом по внешней стороне квадрата. Хотя, возможно, в двумерном случае там и будут ньюансы.
Тут важно понять простую вещь. Что разность городов на восток и запад, а также на север - юг от столицы должна быть минимальна. Не расстояний - они образуются сами, а именно количества городов. Или количества жителей, если император заботится о социальной справедливости.

0

Сообщение от Байт Если квадрат занят, так берем ближайшие пустые места (в смысле заданной метрики) простым обходом по внешней стороне квадрата.

Ближайшие пустые места не равноценны. Нужно выбрать из них лучшее.

0

Сообщение от Shamil1 Ближайшие пустые места не равноценны. Нужно выбрать из них лучшее.

Ну вот и выбирайте! Но - из ближайших. Далеко ходить (кодить ) не надо.
И вообще-то, я предупредил

Сообщение от Байт Если бы не это условие, то задача совсем проста.

Сообщение от Байт Но в данном случае дело осложняется тем, что "хорошие" точки уже могут быть заняты

0