Разбор олимпиадной задачи — Дачники

В этой теме 0 ответов, 1 участник, последнее обновление  Васильев Владимир Сергеевич 2 мес., 1 неделя назад.

  • Автор
    Сообщения
  • #5557
    @admin

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

    Всем известно, что дачники – народ странный, почти такой же, как и программисты. Строят они свои дачи непонятно где, да и выращивают там непонятно что и непонятно зачем. А уж как они туда добираются, это другая история: кто на автобусе, кто на электричке, кто на автомобиле, ну а кто-то вовсе пешком ходит от дома и до самого участка. Так что не стоит удивляться, если вдруг Вы узнаете, что некое садоводческое товарищество располагается на острове, а дачники добираются до него самолетом. Да еще и на этом острове может не быть посадочной полосы, так что высадиться на остров можно, только прыгая с парашютом (мы уж не рассматриваем то, как они возвращаются с дач домой). Рассмотрим этот уникальный случай. Пилот всегда старается осуществить высадку парашютистов таким образом, чтобы дачники приземлялись как можно ближе к своим прямоугольным участкам. Пилоту интересно знать: сколько дачников приземлится на свои участки? Помогите ему решить эту задачу!

    Входные данные:
    В первой строке входного файла INPUT.TXT записано натуральное число N (1 ≤ N ≤ 1000) – количество дачников, далее идут N строк, в каждой из которых описаны координаты каждого дачника и его участка:
    X Y X1 Y1 X2 Y2 X3 Y3 X4 Y4
    где
    (X,Y) – координаты приземления парашютиста
    (X1, Y1, X2, Y2, X3, Y3, X4,Y4) – координаты прямоугольного участка на плоскости, указанные последовательно.
    Все координаты – целые числа, не превышающие 50000 по абсолютной величине

    Выходные данные:
    В выходной файл OUTPUT.TXT нужно вывести количество дачников, приземлившихся на свой участок. Попадание на границу участка считается попаданием на участок.

    Пример:
    INPUT.TXT:

    3
    6 6 3 6 6 9 8 7 5 4
    13 5 9 2 9 8 12 8 12 2
    3 2 2 1 2 3 6 3 6 1 

    OUTPUT.TXT : 2

    Визуализация исходных данных:

    На плоскости координат есть несколько прямоугольников. Необходимо определить принадлежит ли точка к своему прямоугольнику. Проверку всех значений лучше сделать в цикле. Лучше для определения принадлежности точки к области использовать площадь. Будем сравнивать площадь всего прямоугольника с суммой площади 4 треугольников, каждый из которых образуется 2 вершинами прямоугольника, принадлежащими одной стороне и точкой приземления дачника. Для вычисления площади треугольника воспользуемся формулой:
    $$S = \frac{1}{2}\cdot((x_2-x_1)\cdot(y_3-y_1) — (x_3-x_1)\cdot(y_2-y_1))$$

    Визуализация решения:

    #include <cmath>
    #include <iostream>
    #include <fstream>
    using namespace std;
    
    struct Point {
      double x, y;
    };
    
    double triangleSqr(Point a, Point b, Point c) {
      return abs(0.5*((b.x-a.x)*(c.y-a.y)-(c.x-a.x)*(b.y-a.y)));
    }
    
    int main() {
      const double limit(10e-8);
      
      ifstream in("input.txt");
      ofstream out("output.txt");
      
      Point a, b, c, d, person;
      int N, k = 0;
      in >> N;
      
      for (int i = 0; i < N; i++) {
        in >> person.x >> person.y >> a.x >> a.y >> b.x >> b.y >> c.x >> c.y >> d.x >> d.y;
        
        double S = triangleSqr(a, b, c) + triangleSqr(b, c, d);
        double PersonS = triangleSqr(a, b, person) + triangleSqr(b, c, person) + 
          triangleSqr(c, d, person) + triangleSqr(d, a, person);
        
        if (PersonS - S <= limit)
          ++k;
      } 
    
      out << k;
    }

    В функции main() с файла считываются исходные данные, а затем, в цикле, обрабатывается каждый входной набор. Для расчета площади прямоугольника — он разбивается на два треугольника (ABCD будет разбит на ABC и BCD). Затем, аналогично, рассчитываются суммы площадей треугольников, образованных стороной прямоугольника и паращютистом.

    Расчет площади треугольника по трем точках вынесен в функцию triangleSqr.

    Сравнение площадей чисел осуществляется с погрешностью, т.к. они дробные.

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