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

@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

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

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

Новые блоги и статьи Все статьи Все блоги /
Программный контроль заполнения реквизита табличной части документа Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: реализовать контроль заполнения реквизита табличной части. . .	wmic не является внутренней или внешней командой Maks 02.04.2026 Решение: DISM / Online / Add-Capability / CapabilityName:WMIC~~~~ Отсюда: https:/ / winitpro. ru/ index. php/ 2025/ 02/ 14/ komanda-wmic-ne-naydena/	Программная установка даты и запрет ее изменения Maks 02.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: при создании документов установить период списания автоматически. . .	Вывод данных в справочнике через динамический список Maks 01.04.2026 Реализация из решения ниже выполнена на примере нетипового справочника "Спецтехника" разработанного в конфигурации КА2. Задача: вывести данные из ТЧ нетипового документа. . .
Функция заполнения текстового поля в реквизите формы документа Maks 01.04.2026 Алгоритм из решения ниже реализован на нетиповом документе "ВыдачаОборудованияНаСпецтехнику" разработанного в конфигурации КА2, в дополнении к предыдущему решению. На форме документа создается. . .	К слову об оптимизации kumehtar 01.04.2026 Вспоминаю начало 2000-х, университет, когда я писал на Delphi. Тогда среди программистов на форумах активно обсуждали аккуратную работу с памятью: нужно было следить за переменными, вовремя. . .	Идея фильтра интернета (сервер = слой+фильтр). Hrethgir 31.03.2026 Суть идеи заключается в том, чтобы запустить свой сервер, о чём я если честно мечтал давно и давно приобрёл книгу как это сделать. Но не было причин его запускать. Очумелые учёные напечатали на. . .	Модель здравосоХранения 6. ESG-повестка и устойчивое развитие; углублённый анализ кадрового бренда anaschu 31.03.2026 В прикрепленном документе раздумья о том, как можно поменять модель в будущем

@bormant Модератор 7816 / 4635 / 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

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

Решение