! 可能包含一些剧透

link

tag : 构造

题目大意：给 $n$ 个二维平面上的点，求一个排列使得 $P$ 对任意 $i$ 有 $\angle{P_iP_{i + 1}P_{i + 2}}$ 为锐角。$n \le 5000$ 。

题解： 每次从没有使用过的点中选择离当前点距离最远的点，作为下一个点即可。 难以想到的简单的初中几何原理。

link

tag : 几何

题目大意：给 $n$ 个二维平面上的点，求在这些点两两连成的所有直线中，与原点距离第 $k$ 大的。$ n \le 10 ^ 5$

题解：在圆外两点连线与圆相交时，设他们的切线在圆上弧度分别为 $[l_1, r_1], [l_2, r_2]$，那么当这两个区间相交（不包括包含）时，直线与圆相离。 可以画图感受一下

link

题目大意：给一个长度为 $n$ 的序列 $a$ ，求出最长的 subarray ，使得 subarray 中的众数不唯一。$n \le 2 \times 10 ^5, a_i \in [1, A]$。

Subtask 1 : $A \le 100$ ；Subtask 2 : $A \le n$

题解：设整个序列的众数为 f，那么 f 也一定是 subarray 中的众数之一。 Subtask 1 $O(n)$ 枚举另一个众数； Subtask 2 需要分块。出现次数多的数 $O(n)$ 暴力求，出现次数少的可以 $O(T^2)$ 求，T 是出现次数。