Разбор олимпиадной задачи — Сотовая связь в большом городе

Технология и методы программирования Спортивное программирование Структуры данных Разбор олимпиадной задачи — Сотовая связь в большом городе

  • В этой теме 0 ответов, 1 участник, последнее обновление 6 месяцев назад сделано Васильев Владимир Сергеевич.
Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #6266
      @admin
      StudLance.ru

      Условие задачи взято с сайта acmp.ru (Время: 1 сек. Память: 16 Мб Сложность: 35%):

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

      Каждая базовая станция характеризуется своими координатами (для простоты размерами базовых станций пренебрегаем) и радиусом надежной связи (если абонент находится на расстоянии, не превосходящем этот радиус, от базовой станции, то она может использоваться для работы с ним — передачи ему сигналов и приема сигналов от него).

      Известный производитель сотовых телефонов Mokea планирует оснастить свою новую модель сотового телефона функцией определения базовых станций, с которыми может работать абонент. Вам же предстоит написать программу, которая по местоположению абонента для каждого оператора определит, сколько базовых станций этого оператора могут работать с абонентом.

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

      Первая строка входного файла INPUT.TXT содержит целое число n (1 ≤ n ≤ 10000) — количество базовых станций в городе. Далее идут описания этих базовых станций. Каждое описание занимает две строки. На первой расположено название оператора сотовой связи, которому принадлежит эта базовая станция, а на второй — три целых числа x, y, r (-10000 ≤ x, y ≤ 10000, 1 ≤ r ≤ 10000) — соответственно ее координаты и радиус надежной связи. Последняя строка входного файла содержит два целых числа xa, ya (-10000 ≤ xa, ya ≤ 10000) — координаты абонента.

      Все координаты во входном файле даны в одной и той же декартовой прямоугольной системе координат. Названия операторов — это непустые строки длиной не более 50 символов, состоящие из цифр, строчных и прописных букв английского алфавита. Прописные и строчные буквы английского алфавита различаются (например, MPS и mps — два разных оператора).

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

      На первой строке выходного файла OUTPUT.TXT выведите число k – количество операторов сотовой связи, работающих в городе (разумеется, два оператора считаются разными, если их названия не совпадают). Далее выведите k строк. Каждая из этих строк должна содержать название оператора и количество базовых станций этого оператора, доступных абоненту. Первым должно идти название оператора, число базовых станций должно быть отделено от него одним пробелом. В этом списке операторы должны быть перечислены в том же порядке, в каком они встречаются во входном файле (см. примеры). Гарантируется, что k ≤ 100.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 5
      Megahorn
      0 0 10
      BeepLine
      10 10 10
      MPS
      0 0 10
      Ele2
      0 0 1
      SkyPink
      100 100 10
      5 5
      5
      Megahorn 1
      BeepLine 1
      MPS 1
      Ele2 0
      SkyPink 0
      2 3
      Megahorn
      0 0 10
      MPS
      1 1 10
      Megahorn
      2 2 10
      1 1
      2
      Megahorn 2
      MPS 1

      Разбор решения задачи

      Визуализация к задаче:

      В этой задаче нужно перебрать все станции и для каждой из них определить входит в ее зону абонент или нет. Абонент внутри зоны если расстояние от него до станции меньше радиуса действия станции. Структуру для Позиции абонента и станции, а также функции ввода позиции и расстояния между ними возьмем из статьи: Расстояние между точками на С++.

      Входом является набор станций, а в выходной файл нужно поместить количество действующих операторов. Станции принадлежат какому-либо из операторов. Соответствующее отношение можно задать с помощью словаря, где оператор является ключом:

      map<string, vector<Station>> operators;

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

      Затем, переберем всех операторов, для каждого из них — все станции и посчитаем сколько из них доступно нашему абоненту. Особенность этой части задания в том, что операторов требуется перебирать в порядке их появления во входном файле — поэтому сохраним этот порядок с использованием вектора:

      #include <fstream>
      #include <vector>
      #include <map>
      #include <string>
      #include <algorithm>
      #include <cmath>
      
      using namespace std;
      
      struct Position {
        int x, y;
        Position(int _x, int _y)
          : x(_x), y(_y) {
        }
      };
      
      struct Station {
        Position position;
        int radius;
      
        Station() : position(0, 0), radius(0) {
        }
      };
      
      istream& operator >>(istream& ist, Position& position) {
        ist >> position.x >> position.y;
        return ist;
      }
      
      istream& operator>>(istream& ist, Station& station) {
        ist >> station.position >> station.radius;
        return ist;
      }
      
      double distance(const Position& a, const Position& b) {
        double dx = a.x-b.x, dy = a.y-b.y;
        return sqrt(dx*dx + dy*dy);
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        size_t k;
        ifst >> k;
      
        map<string, vector<Station>> operators;
        vector<string> names;
      
        for (size_t i = 0; i < k; ++i) {
          string name;
          Station station;
      
          ifst >> name >> station;
      
          auto it = operators.find(name);
          if (it == operators.end()) { // is new operator
            names.push_back(name);
            operators.insert(make_pair(name, vector<Station>({station})));
          }
          else { // is old operator
            it->second.push_back(station);
          }
        }
      
        Position pos(0, 0);
        ifst >> pos;
      
        ofst << operators.size() << endl;
      
        for (auto name : names) {
          auto& stations = operators.find(name)->second;
      
          auto counter = count_if(stations.begin(), stations.end(), [=](const Station& station) {
            return distance(pos, station.position) < station.radius;
          });
      
          ofst << name << " " << counter << endl;
        }
      }
      

      StudLance.ru

Просмотр 0 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×