РЕГИОНАЛЬНАЯ ОЛИМПИАДА 2003 КВАДРАТИКИ В ЧЕТЫРЁХУГОЛЬНИКЕ
Входной файл: chet.txt Выходной файл: стандартный выход Время на тест: 2 секунды Тесты к задаче:Скачать
Прямоугольник ABCD расположен в первой четверти координатной плоскости следующим образом (см. рис.):
точка A имеет координаты (0;0);
точка B лежит на оси OY;
точка D лежит на оси OX.
Задаются координаты точки C (XC;YC). XC, YC – натуральные числа <= 30000.
Через целочисленные координаты сторон АВ и AD прямоугольника ABCD проведены отрезки параллельно осям OX и OY соответственно. Таким образом, вся площадь прямоугольника покрывается сеткой из единичных (1*1) квадратиков. На каждой стороне прямоугольника ABCD выбирается по одной точке с целочисленными координатами:
на стороне AB - точка t 1 с целочисленными координатами (X1;Y1);
на стороне BC - точка t 2 с целочисленными координатами ( X2;Y2);
на стороне CD - точка t 3 с целочисленными координатами ( X3;Y3);
на стороне DA - точка t 4 с целочисленными координатами ( X4;Y4).
Последовательно соединив точки в порядке t1-t2-t3-t4-t1, получаем четырехугольник (назовем его N ), отдельные стороны которого могут вырождаться при совпадении соседних точек.
Необходимо подсчитать количество “полных” (не пересекаемых сторонами четырехугольника N ) единичных (1*1) квадратиков, принадлежащих четырехугольнику N (граничные точки “полных” квадратиков могут лежать на сторонах четырехугольника N).
Данные вводятся из текстового файла Chet.txt.
Результат, в виде целого числа, выводится в свободной строке экрана.
Пример (см. рис.). 5 3 {1-я строка ввода – координаты точки С: < XC> <YC>} 0 2 {2-я строка ввода – координаты точки t1: <X1> <Y1>} 1 3 {3-я строка ввода – координаты точки t2: <X2> <Y2>} 5 1 {4-я строка ввода – координаты точки t3: <X3> <Y3>} 2 0 {5-я строка ввода – координаты точки t4: <X4> <Y4>} 2 {1-я строка вывода: <количество “полных” квадратиков в четырехугольнике N>}.