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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Знаешь почему 90% людей редко бывают счастливыми? kumehtar 14.04.2026 Потому что они ждут. Ждут выходных, ждут отпуска, ждут удачного момента. . . а удачный момент так и не приходит.	Фиксация колонок в отчете СКД Maks 14.04.2026 Фиксация колонок в СКД отчета типа Таблица. Задача: зафиксировать три левых колонки в отчете. Процедура ПриКомпоновкеРезультата(ДокументРезультат, ДанныеРасшифровки, СтандартнаяОбработка) / / . . .	Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .
Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .	Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .

@bormant Модератор 7818 / 4637 / 2837 Регистрация: 22.11.2013 Сообщений: 13,159 Записей в блоге: 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

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

Решение