Разбор acmp — Две окружности

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

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

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

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

      Входной файл INPUT.TXT состоит из двух строк. На каждой строке записана информация об одной окружности – координаты ее центра x и y (целые числа, по модулю не превосходящие 5000) и радиус (целое число 1 ≤ r ≤ 1000).

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

      В выходной файл OUTPUT.TXT выведите «YES», если окружности имеют хотя бы одну общую точку, и «NO» в противном случае.

      Примеры

      INPUT.TXT OUTPUT.TXT
      1 0 0 2
      0 3 2
      YES
      2 1 1 1
      4 4 1
      NO

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

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

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

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

      Во вторых трех случаях центр одной окружности находится внутри другой:

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

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

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

      #include <fstream>
      #include <cmath>
      
      using namespace std;
      
      double distance(double a_x, double a_y,
                      double b_x, double b_y) {
        double dx = a_x-b_x, dy = a_y-b_y;
        return sqrt(dx*dx + dy*dy);
      }
      
      bool is_close(const double a, const double b, const double epsilon = 0.00001) {
          return std::fabs(a - b) < epsilon;
      }
      
      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int a_x, a_y, a_r, b_x, b_y, b_r;
        ifst >> a_x >> a_y >> a_r >> b_x >> b_y >> b_r;
      
        double center_dist = distance(a_x, a_y, b_x, b_y);
        double radius_sum = a_r + b_r;
      
        if (is_close(center_dist, radius_sum)) {
          /* окружности не вложены, пересекаются в одной точке */
          ofst << "YES";
          return 0;
        }
      
        if (center_dist > radius_sum) {
          /* окружности не вложены, не пересекаются */
          ofst << "NO";
          return 0;
        }
      
        /* центр одной окружности находится внутри другой */
      
        if (is_close(center_dist + a_r, b_r) || is_close(center_dist + b_r, a_r)) {
          /* пересекаются в одной точке */
          ofst << "YES";
          return 0;
        }
      
        if (center_dist + a_r < b_r || center_dist + b_r < a_r) {
          /* одна окружность полностью лежит внутри другой */
          ofst << "NO";
          return 0;
        }
      
        /* пересекаются в двух точках */
        ofst << "YES";
      }

      StudLance.ru

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