В городе N есть \(m\) асфальтированных дорог, \(i\)-я дорога представляет собой отрезок между двумя точками \(A_{i}\) и \(B_{i}\) с координатами \((x^{A}_{i}, y^{A}_{i})\) и \((x^{B}_{i}, y^{B}_{i})\) соответственно.
В рамках тестирования новой технологии, которая позволяет переместить дорогу, мэр города N может демонтировать ровно одну любую дорогу и построить в любом месте ровно одну новую дорогу из полученного при демонтаже асфальта, при этом длина новой дороги должна не превосходить длину демонтированной дороги.
Проанализировав бюджет города, мэр понял, что в будущем он сможет обслуживать ровно три асфальтированные дороги.
Поэтому в рамках программы благоустройства мэр хочет выбрать три дороги, которые останутся асфальтированными, а также, возможно, переложить одну из них. Остальные асфальтовые дороги придется превратить в грунтовые. После этого три получившиеся дороги должны образовывать связный асфальтированный участок, то есть между любыми двумя асфальтированными точками должно быть можно добраться по асфальтированным дорогам.
Теперь мэр хочет понять, сколькими способами можно успешно завершить благоустройство города N: выбрать три дороги, чтобы выполнялись описанные условия.
Формат входных данных
В первой строке входных данных дано целое число \(m\) — количество асфальтированных дорог в городе (\(3 \leq m \leq 100\)).
Далее даны \(m\) строк. В \(i\)-й строке записаны четыре целых числа: \(x^{A}_{i}\), \(y^{A}_{i}\), \(x^{B}_{i}\), \(y^{B}_{i}\) — координаты точек \(A_{i}\) и \(B_{i}\) начала и конца \(i\)-й дороги соответственно.
Все координаты точек целые и по абсолютному значению не превосходят \(10^4\). Конечные точки любой дороги различны.
Формат выходных данных
В единственной строке выходных данных выведите одно целое число \(k\) — количество способов выбрать три дороги так, чтобы можно было успешно завершить благоустройство города N.
В примере из условия, чтобы успешно завершить благоустройство города N, можно выбрать три дороги одним из трех способов:
-
дороги \(\{1, 2, 3\}\) с координатами \((1, 1)-(2, 3)\), \((1, 3)-(2, 1)\), \((3, 1)-(4, 3)\) соответственно, и переложить дорогу \(3\), например, на новые координаты \((1, 4)-(2, 2)\)
-
дороги \(\{1, 2, 4\}\) с координатами \((1, 1)-(2, 3)\), \((1, 3)-(2, 1)\), \((2, 6)-(3, 6)\) соответственно, и переложить дорогу \(4\), например, на новые координаты \((1, 2)-(2, 2)\)
-
дороги \(\{2, 3, 4\}\) с координатами \((1, 3)-(2, 1)\), \((3, 1)-(4, 3)\), \((2, 6)-(3, 6)\) соответственно, и переложить дорогу \(4\), например, на новые координаты \((2, 1)-(3, 1)\)
Иллюстрация к способу a)
Перекладывание \(3\)-й дороги с координат \((3, 1)-(4, 3)\) на новые координаты \((1, 4)-(2, 2)\)
Иллюстрация к способу b)
Перекладывание \(4\)-й дороги с координат \((2, 6)-(3, 6)\) на новые координаты \((1, 2)-(2, 2)\)
Иллюстрация к способу c)
Перекладывание \(4\)-й дороги с координат \((2, 6)-(3, 6)\) на новые координаты \((2, 1)-(3, 1)\)