Разбор олимпиадной задачи — Сжимающий оператор

Просмотр 0 веток ответов
  • Автор
    Сообщения
    • #5982
      @admin
      StudLance.ru

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

      Оператором А, действующим из множества Х в множество Y (или просто оператором из X в Y) называется правило, согласно которому каждому элементу x множества X сопоставляется элемент y=Ax из множества Y. Пусть X и Y – множества точек на плоскости. Оператор A из X в Y называется сжимающим с коэффициентом q, где q – вещественное число из полуинтервала [0, 1), если для любого x из X выполнено ||Ax|| <= q*||x|| (здесь ||x|| — норма точки x – расстояние от x до начала координат). Проще говоря, оператор называется сжимающим с коэффициентом q если он сопоставляет каждой точке точку, которая не менее, чем в q раз ближе к началу координат.

      Для заданного оператора А требуется проверить является ли он сжимающим с коэффициентом q.

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

      Первая строка входного файла INPUT.TXT содержит количество точек n (1 < = n <= 100) и число q (0 <= q < 1), заданное не более чем с 3 знаками после десятичной точки. Следующие n строк содержат по 4 целых числа, по модулю не превосходящих 1000, разделенные пробелами – координаты точки множества X и сопоставленной ей точки из множества Y.

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

      В выходной файл OUTPUT.TXT выведите одно слово: “Yes” если оператор является сжимающим с коэффициентом q и “No” в противном случае.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 2 0.5
      0 10 5 0
      10 0 0 1
      Yes
      2 2 0.1
      0 10 5 0
      10 0 0 1
      No
      3 2 0.9
      0 0 0 0
      10 0 0 1
      Yes

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

      Поясняет задачу следующая картинка:

      Для каждой точки множества X с учетом значения q, отржающего свойства оператора можно определить некоторую окрестность, схематично показанную на картинке. Задача — проверить, попадает ли соответствующая точка множества Y в эту окрестность.

      Выглядит очень просто — нам нужно определить расстояние от точки до центра координат, сделать это можно по теореме Пифагора.

      Тогда, нам остается считывать последовательно каждую пару точек и выполнять для них простую проверку:

      #include <fstream>
      using namespace std;
      
      // ...
      
      int main() {
        int n;
        double q;
        const Position center(0, 0);
        
        std::ifstream ifst("input.txt");
        std::ofstream ofst("output.txt");
        
        ifst >> n >> q;
        
        bool isCompressed = true;
        for (int i = 0; i < n; ++i) {
          Position pointA(0, 0), pointB(0, 0);
          ifst >> pointA >> pointB;
          
          auto d_a = distance(pointA, center)*1000;
          auto d_b = distance(pointB, center)*1000;
          
          if(d_a*q < d_b) {
            isCompressed = false;
            break;
          }
        }
        
        if (isCompressed)
          ofst << "Yes";
        else 
          ofst << "No";
      }

      Функцию distance, структуру Position и прочее можно взять по приведенной выше ссылке.

      В этой задаче есть подвох, связанный с точностью. В ряде случаев точка множества Y будет попадать как раз на гриницу окрестности, однако проверить это с помощью оператора == мы не сможем, т.к.не все дробные числа представимы в типе double без потери точности. Точность теряется в младших разрядах чисел, чтобы ее повысить — традиционно числа умножают на некоторый большой коэффициент — за счет этого часть «мантиссы» переводится в «порядок».

      StudLance.ru

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