长训第一周思考题 | Sevenki's Blog

介值定理

一个连续的函数如果在 $f (a)$ 处取到 $c$ ，在 $f (b)$ 处取到 $d$ （ $a < b$ ），那么对于任意的在 $c$ 与 $d$ 之间的数 $k$ 一定存在 $w \in (a, b)$ 使得 $f (w) = k$ 。

平面上有若干点，三点不共线，给你一个坐标 $(x, y)$ ，一定存在一条过 $(x, y)$ 的直线使得两侧点的数量相差至多 1，如果点在直线上，你可以任意指定它在那一侧。

不妨让这个直线是“有向”的，那么它旋转一百八十度后，左侧与右侧点的数量差就会变成相反数。

根据介值定理，一定有取 $0 1$ 的时候。（ $1$ 是因为奇数点数）。

若干棍子，每根棍子质地均匀，各有体积和质量，要求至多切两刀，

将其分为两个集合，质量体积都相等。

假装把这些棍子连接成一个圆，（假定柱子的横截面半径相等，如果不等就拉伸一下）然后随便拉一条圆的直径，容易知道这条直径平分了体积。

不妨让直径为一条有向线段，那么线段的左右侧数量差在旋转一百八十度之后就会取到相反数。

根据介值定理， $0$ 处可以取到。

不妨定平面坐标系中的一维为体积，一维为质量。

那么每个棍子可以被表示为一个向量。把每个向量拼接在一起，那么问题变成了，调整使得体积质量两维度的中点成为某向量的终点，某向量的起点。

我们可以任意排列每个向量。

由于我们切两刀之后，是要把他们所属集合 swap 的（不然就相当于没有操作），那我们对中点分界处的两个向量考虑一下，切一刀其实就是以下过程：

将两个向量各切一刀然后平移一下。

我们发现这个新转折点可以落在以下平行四边形内的任意地方：

类似的方法，可以得出一定有一种方式调整向量的排列顺序使得转折点落在平行四边形之内。

我们称点 $(x, y)$ 在直线 $A x + B y + C = 0$ 上方，当且仅当 $A x + B y + C \geq 0$ 。

你可以任意选定 $n$ 个点（要求三点不共线），然后问 $A, B, C$ 任意取的情况下，有多少种不同的在直线上方的点的集合。

答案至少是 $n^{2}$ 级别的：考虑一个圆上的各点。

答案至多是 $n^{2}$ 级别的：

对于一条直线，我们把他向下平移直到碰到一个点，然后再绕着该点顺时针旋转直到碰到另一点，那么这个直线和这两点构成的直线上方的点构成的集合是一样的。

发现上述方法可以将平面内的直线划分成 $O (n^{2})$ 个等价类。所以答案为 $O (n^{2})$ 。

平面上有若干个点，三点不共线。问是否存在两条直线，将这些点分为 4 个部分，每部分差不超过 1.

首先我们可以先确定一条线，将其评分。

然后我们考虑另外一条线：不妨设其与刚刚那条线的夹角为 $θ$ 。

那么对于每一个 $θ$ ，我们都可以确定一条直线，使得它平分第一条直线的一侧。

那么我们考虑 $θ$ 逐渐增加，套路地，当角旋转到 $θ + π$ 时，第一条直线的另一侧的划分的点数差就变成了相反数。

根据介值定理，相差至多为 $1$ 的地方可以取到。