Определение координат столицы

 
0
 
C++
ava
dima2308 | 14.12.2016, 21:09
Имеется N городов, каждый из которых имеет целые координаты. Расстояние между двумя городами определяется как |x1-x2|+|y1-y2|.
Требуется построить n+1 город и сделать его столицей (координаты должны быть целыми). Место для столицы выбирается так, чтобы среднее арифметическое расстояний между столицей и остальными городами было наименьшим и столица не должна стоять на уже построенном городе.
На вход подается N - количество городов (1<=N<=100); пары целых чисел, не превышающих 1000 по абсолютной величине - координаты городов.
На выходе два целых числа X и Y - координаты столицы.
Пример:
Входные данные
4
0 0
1 1
0 1
1 0
На выходе имеем 0 2

Не могу составить алгоритм решения.
Буду рад любой помощи.
Kommentare (3)
ava
Olej | 18.12.2016, 17:03 #
Цитата (dima2308 @ 14.12.2016,  21:09)
Пример:

Входные данные

4

0 0

1 1

0 1

1 0

На выходе имеем 0 2


Это очень дурной, вырожденный пример для начала решения такой задачи: найденное решение 0 2 здесь является как-раз наихудшим возможным.
А взять для начального тестирования любой задачи неадекватный тест - это заведомо загубить затею.
Как говорит английская поговорка:
Цитата


Дайте дурную кличку вашей собаке, после чего можете её повесить.



P.S. Хотя задача, сама по себе, интересная.
ava
Olej | 18.12.2016, 17:19 #
Цитата (dima2308 @ 14.12.2016,  21:09)
Имеется N городов, каждый из которых имеет целые координаты. Расстояние между двумя городами определяется как |x1-x2|+|y1-y2|.

Требуется построить n+1 город и сделать его столицей (координаты должны быть целыми). Место для столицы выбирается так, чтобы среднее арифметическое расстояний между столицей и остальными городами было наименьшим и столица не должна стоять на уже построенном городе.

На вход подается N - количество городов (1<=N<=100); пары целых чисел, не превышающих 1000 по абсолютной величине - координаты городов.

На выходе два целых числа X и Y - координаты столицы.

Не могу составить алгоритм решения.


1. Ищем размеры поля:
Xmax = max( x1, x2, ...) + 1
Xmin = min( x1, x2, ...) - 1
Ymax = max( y1, y2, ...) + 1
Ymin = min( y1, y2, ...) - 1
Для всех (Xmin ... Xmax) * (Ymin ... Ymax) точек поля просчитываем сумму расстояний D и фиксируем минимум этой величины D.

2. Ищем начальную позицию внутри поля:
X = sum( xi, i=1, n ) / n
Y = sum( yi, i=1, n ) / n
Из 4-х целочисленных позиций, окружающих вещественную позицию (X,Y) выбираем ближайшую.
Итерационно, в цикле, рассчитываем расстояния до каждой Di точки ... и сдвигаем позицию (X, Y) в направлении той точки, расстояние до которой минимально.

3. Используя любую известную реализацию оптимизационного алгоритма с ограничениями (X>0, Y>0) ищем вещественный минимум функции 2-х переменных (X,Y). Из 4-х целочисленных соседей (X,Y) перебираем наилучший.
(хотя это решение: "из пушки по воробьям")

P.S. Кстати, из-за того, что положение начала координат (0,0) чисто условно, можно допустить и отрицательные координаты, а оптимизационные задачи без ограничений всегда решаются на порядок проще.
ava
Olej | 23.12.2016, 00:41 #
[QUOTE=Olej,18.12.2016,  17:19]
Цитата (dima2308 @ 14.12.2016,  21:09)


1. Ищем размеры поля:

Xmax = max( x1, x2, ...) + 1

Xmin = min( x1, x2, ...) - 1

Ymax = max( y1, y2, ...) + 1

Ymin = min( y1, y2, ...) - 1

Для всех (Xmin ... Xmax) * (Ymin ... Ymax) точек поля просчитываем сумму расстояний D и фиксируем минимум этой величины D.



#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
using namespace std;

struct town {
   int x, y;
   town( int x = 0, int y = 0 ) {
      this->x = x; this->y = y;
   }
   town operator +( town shf ) {
      return town( x + shf.x, y + shf.y );
   }
   inline unsigned operator -( const town& t ) {
      return abs( x - t.x ) + abs( y - t.y );
   }
   inline bool operator ==( const town& t ) {
      return x == t.x && y == t.y;
   }
};

ostream& operator <<( ostream& out, const town& t ) {
   char s[ 10 ];
   sprintf( s, "<%+03d,%+03d>", t.x, t.y );
   return out << s;
}

unsigned summa( vector<town>& country, town point ) {
   unsigned ret = 0;
   for( auto &x : country ) ret += ( x - point );   
   return ret;
}


capital1.cc :


#include "capital.h"

int main( int argc, char **argv ) {
   vector<town> country;
   int xmin = 9999, xmax = -9999, ymin = 9999, ymax = -9999;
   while( true ) {
      string s;   
      getline( cin, s );
      if( !cin || 0 == s.length() ) break;
      town p;
      istringstream( s ) >> p.x >> p.y;
      xmin = p.x < xmin ? p.x : xmin;
      xmax = p.x > xmax ? p.x : xmax;
      ymin = p.y < ymin ? p.y : ymin;
      ymax = p.y > ymax ? p.y : ymax;
      country.push_back( p );
   }
   cout  << "городов " << country.size() << " : "; 
   for( auto &p : country ) cout << p << "  ";
   cout << endl;
   xmin -= 1; xmax += 1; ymin -= 1; ymax += 1;
   cout << "границы поля: [" << xmin << "..." << xmax
        << ',' << ymin << "..." << ymax << "]" << endl;
   town capital = { xmin, ymin };
   unsigned distanse = summa( country, capital ), m = 0;
   for( int x = xmin; x <= xmax; x++ )
      for( int y = ymin; y <= ymax; y++ ) {
         town point = { x, y };
         if( find( country.begin(), country.end(), point ) != country.end() ) continue;
         unsigned d = summa( country, point );
         if( d < distanse ) {
            distanse = d;
            capital = point;
         }
         m++;
      }
   cout << "столица " << capital << " среднее расстояние "
        << (float)distanse / country.size() << " число проб " << m << endl;       
}
Registrieren Sie sich oder melden Sie sich an, um schreiben zu können.
Unternehmen des Tages
Вы также можете добавить свою фирму в каталог IT-фирм, и публиковать статьи, новости, вакансии и другую информацию от имени фирмы.
Подробнее
Mitwirkende
  dima2308   Olej
advanced
Absenden