Стас живет в селе Аусомбург, административный центр которого представляет из себя треугольник. Для этого треугольника выполняется следующее:
- его вершины находятся в целочисленных координатах,
- координаты его вершин неотрицательные,
- его вершины не лежат на одной прямой.
Стас называет точку на границе административного центра (то есть на границе треугольника) безопасной, если он может добраться до нее по прямой от хотя бы одной точки прямой \(y = 0\), не пересекая внутренность административного центра.
На рисунке серым цветом изображен административный центр. Первый путь не является корректным, потому что он идет не по прямой. Второй путь не является корректным, потому что он пересекает внутренность административного центра. Третий и четвертый пути являются корректными. Найдите суммарную длину небезопасных частей границы. Можно показать, что эти части являются отрезками и их количество конечно.
Выходные данные
Для каждого набора входных данных выведите единственное вещественное число — ответ на задачу.
Ваш ответ будет считаться правильным, если его абсолютная или относительная ошибка не превосходит \(10^{-9}\). Формально, пусть ваш ответ равен \(a\), а ответ жюри равен \(b\). Ваш ответ будет зачтен, если \(\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-9}\).
Примечание
На рисунке изображены треугольники административных центров для первых трех наборов входных данных. Треугольники пронумерованы в соответствии с тем, к какому набору входных данных они относятся.
В первых двух наборах входных данных все точки на границах административных центрах являются безопасными, поэтому ответ \(0\).
На рисунке ниже черным цветом отмечены небезопасные точки границы административного центра в третьем наборе входных данных:
В четвертом наборе входных данных также все точки границы административного центра являются безопасными.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
8 10
10 4
6 2
4 6
0 1
4 2
14 1
11 2
13 2
0 0
4 0
2 4
0 1
1 1
0 0
|
0.0000000
0
2.0000
0.00
1
|