Столица королевства

@Mikstereo · Регистрация: 05.11.2018

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

В некотором царстве, в некотором государстве было S городов, и все они, судя по главной карте императора, имели целые координаты. В те годы леса были дремучие, дороги же строить умели только параллельно осям координат, так что расстояние между двумя городами определялось как |x1 - x2| + |y1 - y2|.
Император решил построить еще один город - (S+1)-й и сделать его столицей своего государства, при этом координаты столицы также должны выражаться целыми числами. Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.
Входные данные:
В первой строке входного потока два числа, разделенных пробелом - размеры царства (целые числа M - число столбцов и N - число строк в интервале от 1 до 50, на которые размечено королевство)
Во второй строке - количество существующих городов S (0 < S <= 100)
В следующих S строках, записано по два числа - X, Y, разделенных пробелом - координаты существующих городов.
Пример входного файла (input.txt):
5 4
3
2 1
2 4
4 3
Выходные данные:Минимальное среднее расстояние от новой столицы до всех остальных городов с точностью до трех знаков после запятой.
Пример выходного файла (output.txt):
1.667
Мой код :

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var x,y:array[1..10000] of longint;
n,m,i,j,k,s,r:longint;
s1:real;
begin
    s1:=1000000;
    readln(m,n);
    readln(s);
    for i:=1 to s do
      read(x[i],y[i]);
    for i:=1 to m do
      for j:=1 to n do
        begin
            k:=0;
            for r:=1 to s do
                k:=k+abs(i-x[r])+abs(j-y[r]);
                if k/s<s1 
                    then s1:=k/s;
        end;
    writeln(s1:0:3);
end.

Дело в том,что проходит не все тесты.По сути нужна минимальная сумма,да такая, чтобы разность городов на восток и запад, а также на север - юг от столицы должна быть минимальна. Не расстояний - они образуются сами, а именно количества городов.
Помогите пожалуйста!

@bormant · 15.11.2018, 20:48

Корень проблемы здесь: k:=k+abs(i-x[r])+abs(j-y[r]).
Расстояние -- это SqRt(Sqr(i-x[r])+Sqr(j-y[r])), можно искать минимум квадрата расстояния (не извлекать корень).
Хотя нет, в условии модуль.

Добавлено через 4 минуты
Вероятно, проблема в отсутствии проверки на наличие города в точке [i,j], по условию столицу строить там нельзя.
Поскольку количество городов не меняется, каждый раз в цикле делить сумму расстояний на s нет смысла, достаточно сравнивать сами суммы, делить один раз при выводе результата.

Добавлено через 44 секунды
Форматирование должно помогать читать код, а не запутывать, имейте это в виду ;-)

@Mikstereo · 15.11.2018, 20:52 **[ТС]**

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

по условию столицу строить там нельзя

Тогда каков смысл проверять если там нельзя строить?

@bormant · 15.11.2018, 20:54

Pascal
14
15
16
17
18
19
20
21
            for r:=1 to s do begin
                t:=abs(i-x[r])+abs(j-y[r]);
                if t=0 then Break; { совпали с существующим городом }
                k:=k+abs(i-x[r])+abs(j-y[r]);
            end;
            if (t>0) and (k1>k) then k1:=k;  { минимум среди подходящих точек }
...
    WriteLn(k1/s:0:3);

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

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

Тогда каков смысл проверять если там нельзя строить?

Условие такое.

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

Место для столицы следует выбрать так, чтобы среднее арифметическое расстояний между столицей и остальными городами было как можно меньше. Однако, разумеется, столицу нельзя строить на месте существующего города.

Если не проверите, то есть шанс, что выбранное место совпадет с имеющимся городом, а это запрещено по условию.

@Mikstereo · 15.11.2018, 21:18 **[ТС]**

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

что выбранное место совпадет с имеющимся городом, а это запрещено по условию

Согласен.Не заметил этого.

Новые блоги и статьи Все статьи Все блоги /
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и напряжениями. Надо найти токи в ветвях. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и решает её. Последовательность действий:. . .
Новый CodeBlocs. Версия 25.03 palva 04.01.2026 Оказывается, недавно вышла новая версия CodeBlocks за номером 25. 03. Когда-то давно я возился с только что вышедшей тогда версией 20. 03. С тех пор я давно снёс всё с компьютера и забыл. Теперь. . .	Модель микоризы: классовый агентный подход anaschu 02.01.2026 Раньше это было два гриба и бактерия. Теперь три гриба, растение. И на уровне агентов добавится между грибами или бактериями взаимодействий. До того я пробовал подход через многомерные массивы,. . .	Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Programma_Boinc 28.12.2025 Советы по крайней бережливости. Внимание, это ОЧЕНЬ длинный пост. Налог на собак: https:/ / ********/ gallery/ V06K53e Финансовый отчет в Excel: https:/ / ********/ gallery/ bKBkQFf Пост отсюда. . .	Кто-нибудь знает, где можно бесплатно получить настольный компьютер или ноутбук? США. Programma_Boinc 26.12.2025 Нашел на реддите интересную статью под названием Anyone know where to get a free Desktop or Laptop? Ниже её машинный перевод. После долгих разбирательств я наконец-то вернула себе. . .

@bormant Модератор 7816 / 4635 / 2837 Регистрация: 22.11.2013 Сообщений: 13,158 Записей в блоге: 1
	15.11.2018, 20:48
	Корень проблемы здесь: k:=k+abs(i-x[r])+abs(j-y[r]). Расстояние -- это SqRt(Sqr(i-x[r])+Sqr(j-y[r])), можно искать минимум квадрата расстояния (не извлекать корень). Хотя нет, в условии модуль. Добавлено через 4 минуты Вероятно, проблема в отсутствии проверки на наличие города в точке [i,j], по условию столицу строить там нельзя. Поскольку количество городов не меняется, каждый раз в цикле делить сумму расстояний на s нет смысла, достаточно сравнивать сами суммы, делить один раз при выводе результата. Добавлено через 44 секунды Форматирование должно помогать читать код, а не запутывать, имейте это в виду ;-) 1

Столица королевства

Решение