Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Для новичков > Определение координат столицы

Автор: 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

Не могу составить алгоритм решения.
Буду рад любой помощи.

Автор: 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. Хотя задача, сама по себе, интересная.

Автор: 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) чисто условно, можно допустить и отрицательные координаты, а оптимизационные задачи без ограничений всегда решаются на порядок проще.

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

Цитата(dima2308 @ 14.12.2016, 21:09)

Буду рад любой помощи.

Язык?

Автор: Olej 23.12.2016, 00:41

Цитата(Olej @ 18.12.2016, 17:19)

Код


#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;       
}

Добавлено @ 00:42

Цитата(Olej @ 18.12.2016, 17:19)

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

Код


#include "capital.h"

int main( int argc, char **argv ) {
   vector<town> country;
   double xm = 0, ym = 0;
   while( true ) {
      string s;   
      getline( cin, s );
      if( !cin || 0 == s.length() ) break;
      town p;
      istringstream( s ) >> p.x >> p.y;
      xm += p.x;
      ym += p.y;
      country.push_back( p );
   }   
   cout  << "городов " << country.size() << " : "; 
   for( auto &p : country ) cout << p << "  ";
   cout << endl;
   town cp( xm / country.size(), ym / country.size() );
   unsigned dist = summa( country, cp ), m = 1;
   bool bstp;
   do {
      town neib[] = {
         { 1, 0 }, { 1, 1 }, { 0, 1 }, { -1, 1 },
         { -1, 0 }, { -1, -1 }, { 0, -1 }, { 1, -1 }
      };
      bstp = false;
      town pm;
      for( auto &p : neib ) {
         town pc = cp + p;
         if( find( country.begin(), country.end(), pc ) != country.end() )
            continue;
         unsigned d = summa( country, pc ); //  cp + p );
         if( d < dist ) {
            dist = d;
            pm = pc; // cp + p;
            bstp = true;
         }
         m++;
      }
      if( bstp ) cp = pm;
   } while( bstp );   
   cout << "столица " << cp << " среднее расстояние "
        << (float)dist / country.size() << " число проб " << m << endl;
}

Добавлено через 5 минут и 44 секунды

Код


[olej@dell capital]$ ./capital1 < country.4
городов 4 : <+00,+03>  <+03,+00>  <+00,-03>  <-03,+00>
границы поля: [-4...4,-4...4]
столица <+00,+00> среднее расстояние 3 число проб 77

[olej@dell capital]$ ./capital2 < country.4
городов 4 : <+00,+03>  <+03,+00>  <+00,-03>  <-03,+00>
столица <+00,+00> среднее расстояние 3 число проб 9

Код


[olej@dell capital]$ ./capital1 < country.80
городов 8 : <-20,-20>  <-10,+10>  <+10,+30>  <+30,+40>  <+60,+30>  <+50,+00>  <+30,-10>  <+10,-20>
границы поля: [-21...61,-21...41]
столица <+10,+00> среднее расстояние 42.5 число проб 5221

[olej@dell capital]$ ./capital2 < country.80
городов 8 : <-20,-20>  <-10,+10>  <+10,+30>  <+30,+40>  <+60,+30>  <+50,+00>  <+30,-10>  <+10,-20>
столица <+20,+07> среднее расстояние 42.5 число проб 9

Код


[olej@dell capital]$ ./capital1 < country.800
городов 8 : <-200,-200>  <-100,+100>  <+100,+300>  <+300,+400>  <+600,+300>  <+500,+00>  <+300,-100>  <+100,-200>
границы поля: [-201...601,-201...401]
столица <+100,+00> среднее расстояние 425 число проб 484201

[olej@dell capital]$ ./capital2 < country.800
городов 8 : <-200,-200>  <-100,+100>  <+100,+300>  <+300,+400>  <+600,+300>  <+500,+00>  <+300,-100>  <+100,-200>
столица <+200,+75> среднее расстояние 425 число проб 9