题目背景

百度之星 2026 决赛 T7

原题时限 8s，但是洛谷开不下就先放 5s 吧。

题目描述

小鸥对无穷的宇宙感到好奇。

小鸥在夜里常常凝视着星空，想象着发生在地球之外有多少有趣、感人的故事，又有多少五彩斑斓、震撼人心的景象。

一天，小鸥决定寻找星空中有多少优美的星星组。于是，她在图纸上标出了 \(n\) 颗星星，其中第 \(i\) 颗星星位于 \((x_i,y_i)\)。所有星星的坐标均为整数，任意两颗星星的位置不同，但允许三颗或更多星星共线。

小鸥认为，由三颗星星组成的星星组是 优美的，当且仅当这三颗星星围成的三角形面积恰为 \(\frac12\)。

小鸥想知道，这 \(n\) 颗星星中有多少个优美的星星组。请你帮她回答这个问题！

输入格式

第一行一个正整数 \(T\)（\(1\le T\)），表示测试数据组数。

对于每组测试数据，第一行一个正整数 \(n\)（\(3\le n\le 5000\)），表示星星的数量。

接下来 \(n\) 行，每行两个整数 \(x_i,y_i\)（\(\vert x_i\vert,\vert y_i\vert\le 10^8\)）表示第 \(i\) 颗星星的位置。保证每颗星星的位置互不相同。

对于所有测试数据，保证 \(\sum n^2\le2.5\times 10^7\) 且 \(\sum n\le 10^5\)。

输出格式

对于每组测试数据，输出一行，包含一个整数，表示答案。

输入输出样例 #1

输入 #1

3
3
0 0
3 1
1 0
4
0 0
1 0
0 1
1 1
10
0 0
2 1
-2 1
0 2
0 -2
3 -1
-3 -1
1 3
-1 3
2 -3

输出 #1

1
4
5

说明/提示

对于测试数据 \(1\)，三颗星星刚好构成优美的星星组。

对于测试数据 \(2\)，四颗星星位于一个边长为 \(1\) 的正方形的四个顶点上。任取其中三颗星星，它们围成的三角形面积均为 \(\frac12\)，因此答案为 \(4\)。

对于测试数据 \(3\)，各颗星星的位置以及 \(5\) 个优美的星星组如下图所示。