I подход – через площади

Рис. 37. Проверка принадлежности точки треугольнику через площади

Рис. 38. Формула Герона для вычисления площади треугольника по его сторонам

Рис. 39. Формула вычисления площади треугольника по координатам его вершин

Задача №205.  Дачники(acmp.ru)

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

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

В первой строке записано натуральное число 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 по абсолютной величине

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

Вывести количество дачников, приземлившихся на свой участок.

Пример

Решение

Эта задача является разновидностью рассмотренной ранее задачи «Точка и многоугольник». Дачник попадёт на свой участок, если сумма площадей треугольников, которые образуют отрезки, соединяющие его с угловыми точками участка, не превышает площади прямоугольника.

Пронумеруем эти точки 0 – место приземления дачника, 1, 2, 3, 4 – углы участка (см.рис.)

Для нахождения площадей воспользуемся формулой косого произведения, описанной ранее в главе.Площадь прямоугольника

не должна быть меньше суммы

#include <iostream>

#include <cmath>                //функция abs

using namespace std;

int x[5], y[5], n, i, count = 0, s;

//вычислениеудвоенной площади треугольника

int area(inta, intb, intc) {  

return abs((y[b] - y[a]) * (x[c] - x[a])

       - (x[b] - x[a]) * (y[c] - y[a]));

}

int main() {

cin >> n;

for (; n--;){

   for(i = 0; i < 5; i++)

       cin >> x[i] >> y[i];

   s = 2 * area(1, 2, 3);

   for(i=1; i<5; i++)

       s -= area (0, i, (i<4 ? i+1 : 1));

   count += (s>=0);

}

cout << count;

}

Задача №206.  Спичечная модель