{"extraResources":{"example.01.mu":"TVXzATINCiFjMTs1DQowIDAgMCAxMA0KMCA1IDMgMTANCjAgNSAzIDANCjAgNSA3IDQNCjAgNSA2IDINCiFjMjs4DQowIDAgMTAgMTANCjMgNCA0IDQNCjQgNCA0IDUNCjMgNCA0IDQNCjcgNyA3IDgNCjcgNyA4IDcNCjUgNSA0IDYNCjUgNSAzIDcNCg=="},"scoring":null,"notes":"","legend":"Let's say that three segments on a plane form a {\\it K-shaped figure} if:\r\n\\begin{shortitems}\r\n\\item two of them share a common endpoint;\r\n\\item this common endpoint lies strictly inside the third segment;\r\n\\item these two segments are located on the same side with respect to the third one;\r\n\\item all three segments are pairwise not collinear.\r\n\\end{shortitems} \r\n\r\n\\begin{center}\r\n  \\begin{tabular}{c|c}\r\n    \\includegraphics{kShaped-1.eps} & \\includegraphics{kShaped-2.eps}\\\\\r\n    \\small{Valid K-shaped figures} & \\small{Invalid K-shaped figures}\r\n  \\end{tabular}\r\n\\end{center}\r\n\r\nYou are given a collection of $n$ segments on the plane. Find the number of triples of segments from this collection that form a K-shaped figure.","authorLogin":"tourist","language":"english","timeLimit":3000,"output":"For each test case, print a single integer~--- the number of triples of segments that form a K-shaped figure.","inputFile":"stdin","outputFile":"stdout","input":"Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \\le t \\le 3333$). The description of the test cases follows.\r\n\r\nThe first line of each test case contains a single integer $n$~--- the number of segments ($3 \\le n \\le 1000$).\r\n \r\nThe $i$-th of the following $n$ lines contains four integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$, $y_{i,2}$~--- the coordinates of endpoints of the $i$-th segment ($-10^6 \\le x_{i,1}, y_{i,1}, x_{i,2}, y_{i,2} \\le 10^6$). All segments have positive lengths. Some segments may coincide.\r\n\r\nIt is guaranteed that the sum of $n$ over all test cases does not exceed $10^4$.","authorName":"Gennady Korotkevich","sampleTests":[{"output":"6\r\n2\r\n","input":"2\r\n5\r\n0 0 0 10\r\n0 5 3 10\r\n0 5 3 0\r\n0 5 7 4\r\n0 5 6 2\r\n8\r\n0 0 10 10\r\n3 4 4 4\r\n4 4 4 5\r\n3 4 4 4\r\n7 7 7 8\r\n7 7 8 7\r\n5 5 4 6\r\n5 5 3 7\r\n","inputFile":"example.01","outputFile":"example.01.a"}],"name":"K-Shaped Figures","interaction":null,"memoryLimit":536870912,"tutorial":"{\r\n    \\parindent=1cm\r\n    \\begin{tabular}{l@{\\extracolsep{1cm}}l}\r\n         Идея: & Геннадий Короткевич\\\\\r\n         Разработка: & Павел Кунявский\\\\\r\n     \\end{tabular}\r\n} \r\n\r\nТривиальное решение состоит в переборе всех троек отрезков и проверки условия задачи для каждого такой тройки. Такое решение будет требовать $O(n^3)$ проверок и является слишком долгим.\r\n\r\nДля ускорения заметим, что одно из условий достаточно сильно ограничивает возможные хорошие тройки отрезков. А именно, если перебрать отрезок, являющийся <<основанием>> буквы K, то все остальные отрезки можно разбить на группы по общему концу, лежащему на этом отрезке, за линейное время с помощью хеш-таблицы, или за $O(n\\log{n})$ с помощью сортировки. В качестве двух других отрезков в тройке с отрезком-<<основанием>> имеет смысл выбирать только отрезки из одной группы. Однако, если почти все отрезки будут сходиться в одной точке, такое решение все еще будет работать за $O(n^3)$, хоть и с заметно более хорошей скрытой константой.\r\n\r\nДля достаточно быстрого решения необходимо научиться обрабатывать каждую группу за около-линейное время. В группе нужно найти отрезки, которые будут направлены в одну сторону относительно основания, и при этом не сонаправлены друг с другом. Для этого нужно найти количество пар, направленных в одну сторону относительно отрезка (что легко сделать за линейное время, посчитав количество направленных в каждую из двух сторон), и вычесть количество пар сонаправленных. Для подсчёта последнего количества нужно отнормировать каждый вектор, соответствующий отрезку, чтобы сонаправленные вектора стали одинаковыми, и посчитать количество пар одинаковых. Для нормировки вектора можно поделить на их длину или, чтобы обойтись без вещественных чисел, на наибольших общий делитель их координат. Количество пар одинаковых можно найти, сгруппировав одинаковые отрезки с помощью хеш-таблицы или сортировки. Такое решение потребует $O(n)$ или $O(n\\log{n})$ времени в зависимости от реализации.\r\n\r\nТакие образом, суммарное время работы решения составит $O(n^2)$ или $O(n^2\\log{n})$."}