308648: CF1552C. Maximize the Intersections
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Maximize the Intersections
题意翻译
在一个圆上有 $2n$ 个不同的点,具有以下性质:无论你如何选择 $3$ 条连接 $3$ 对互不相干的点的弦,在圆内没有一个点严格属于所有 $3$ 条弦。这些点按顺时针顺序被编号为 $1,2, \ldots ,2n$。 最初,$k$ 条和弦连接了 $k$ 对点,其方式是这些和弦的所有 $2k$ 个端点是不同的。 你想画出 $n-k$ 条额外的和弦,连接剩余的 $2(n-k)$ 个点(每个点必须正好是一个和弦的端点)。 最后,让 $x$ 成为所有 $n$ 条弦的交叉点的总数。计算如果你以最佳方式选择 $n - k$ 条弦,$x$ 能达到的最大值。 请注意,$2n$ 个点的确切位置并不重要,只要第一段中所述的属性成立即可。题目描述
On a circle lie $ 2n $ distinct points, with the following property: however you choose $ 3 $ chords that connect $ 3 $ disjoint pairs of points, no point strictly inside the circle belongs to all $ 3 $ chords. The points are numbered $ 1, \, 2, \, \dots, \, 2n $ in clockwise order. Initially, $ k $ chords connect $ k $ pairs of points, in such a way that all the $ 2k $ endpoints of these chords are distinct. You want to draw $ n - k $ additional chords that connect the remaining $ 2(n - k) $ points (each point must be an endpoint of exactly one chord). In the end, let $ x $ be the total number of intersections among all $ n $ chords. Compute the maximum value that $ x $ can attain if you choose the $ n - k $ chords optimally. Note that the exact position of the $ 2n $ points is not relevant, as long as the property stated in the first paragraph holds.输入输出格式
输入格式
The first line contains a single integer $ t $ ( $ 1 \le t \le 100 $ ) — the number of test cases. Then $ t $ test cases follow. The first line of each test case contains two integers $ n $ and $ k $ ( $ 1 \le n \le 100 $ , $ 0 \le k \le n $ ) — half the number of points and the number of chords initially drawn. Then $ k $ lines follow. The $ i $ -th of them contains two integers $ x_i $ and $ y_i $ ( $ 1 \le x_i, \, y_i \le 2n $ , $ x_i \ne y_i $ ) — the endpoints of the $ i $ -th chord. It is guaranteed that the $ 2k $ numbers $ x_1, \, y_1, \, x_2, \, y_2, \, \dots, \, x_k, \, y_k $ are all distinct.
输出格式
For each test case, output the maximum number of intersections that can be obtained by drawing $ n - k $ additional chords.
输入输出样例
输入样例 #1
4
4 2
8 2
1 5
1 1
2 1
2 0
10 6
14 6
2 20
9 10
13 18
15 12
11 7
输出样例 #1
4
0
1
14