Точка пересечения отрезков

Для определения места пересечения отрезков (если известно, что они пересекаются), достаточно определить точку пересечения прямых, на которых эти отрезки лежат.

Пусть A₁x+B₁y+C₁=0— уравнение прямой, проходящей через концевые точки первого отрезка, а А₂х+ В₂у+С₂=0 — уравнение прямой, проходящей через концевые точки второго отрезка.

Тогда для определения точки пересечения отрезков достаточно решить систему уравнений

Домножив первое уравнение на А₂, а второе — на А₁ получим

Вычитаем из первого уравнения второе и находим значение у:

Аналогично вычисляем значение х:

Это справедливо в случае, если А₂*В₁—А₁*В₂<>0. Но мы уже знаем, что отрезки пересекаются и не лежат на одной прямой, а это невозможно, если А₂*В₁—А₁*В₂ =0.

Задание

Задание 1. Концы отрезка на плоскости имеют целочисленные координаты. Требуется написать программу, которая вычислит, сколько всего точек с целочисленными координатами принадлежат этому отрезку, граничные точки включаются.

Для произвольных (x₁, y₁) и (x₂, y₂), нужно брать все целые значения между x₁ и x₂ и проверять значение y в полученных точках.
Для целочисленных (x₁, y₁) и (x₂, y₂) можно так:
n = НОД(|x₂ − x₁|, |y₂ − y₁|)
dx = (x₂ − x₁) // n
dy = (y₂ − y₁) // n
И взять все пары (x₁ + dx × i, y₁ + dy × i) для i = 1.. n − 1

Входные данные
Входной файл INPUT.TXT содержит четыре числа – координаты концов отрезка (x₁, y₁) и (x₂, y₂). Каждая из координат не превышает по абсолютной величине значения 109.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число – количество точек на заданном отрезке, имеющих целочисленные координаты.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	1 1 2 2	2
2	0 0 -2 -2	3
3	1 1 1 10	10

Задание 2. Эта история происходила на одной плоской планете. С незапамятных времен на ней существовал город N, находящийся в точке xn,yn. Кроме этого, в разное время на этой же планете существовали страны, каждая из которых имела форму треугольника.
Теперь перед историками встала серьезная задача — по имеющимся у них данным о треугольных странах определить, в какие страны мог входить город N. Город мог входить в страну, если он находится строго внутри нее.

Входные данные
Первая строка входного файла содержит два числа: xn и yn — координаты города N. Вторая строка входного файла содержит количество k треугольных стран (1 ≤ k ≤ 1000).

Последующие k строк каждая описывают одну треугольную страну. Описание треугольной страны состоит из шести целых чисел x1,y1,x2,y2,x3,y3, где (x1,y1), (x2,y2), (x3,y3) — координаты вершин этой страны.

Гарантируется, что все страны имеют ненулевую площадь. Все координаты не превосходят 10000 по абсолютной величине.

Выходные данные
В первой строке выходного файла выведите количество стран, в которые мог входить город N.

Во второй строке выведите через пробел номера этих стран в возрастающем порядке. Страны нумеруются с единицы в том порядке, в каком они заданы во входном файле.

Примеры

№	INPUT.TXT	OUTPUT.TXT
1	0 1 2 -2 0 2 0 0 2 -3 0 3 0 0 3	2 1 2
2	0 2 2 -2 0 2 0 0 2 -3 0 3 0 0 3	1 2

Задание 3. Дан набор из нескольких отрезков. Необходимо составить треугольник наибольшей площади, используя в качестве сторон три отрезка из заданных. Требуется написать программу, которая найдет наибольшую площадь треугольника.

Входные данные
Входной файл INPUT.TXT содержит в первой строке одно целое число N (3 ≤ N ≤ 1000) – количество отрезков.

Во второй строке содержатся N целых чисел от 1 до 1000 – длины отрезков. Числа разделены пробелом.

Выходные данные
Выходной файл OUTPUT.TXT должен содержать одно число с тремя десятичными знаками после запятой – наибольшую площадь треугольника из заданных отрезков. Если из заданных отрезков нельзя построить ни одного треугольника, то вывести в файл 0.

Примеры