题解 | #Strange_Functions#

题意是给出 $nn$ 个奇怪的函数 $f_1(x),f_2(x),\cdots ,f_n(x)f\_1(x),f\_2(x),\backslash cdots,f\_n(x)$，对每个函数 $f_i(x)f\_i(x)$ 分别判断是否存在 $x_i\in \mathbb{R}x\_i\; \backslash in\; \backslash mathbb\{R\}$ 使得 $f_i(x_i)f\_i(x\_i)$ 是 $f_1(x_i),f_2(x_i),\cdots ,f_n(x_i)f\_1(x\_i),f\_2(x\_i),\backslash cdots,f\_n(x\_i)$ 之中的严格最小值。数据范围是 $n\le 10^{5}n\; \backslash le\; 10^5$，$1\le k_i\le 10^{5}1\; \backslash le\; k\_i\; \backslash le\; 10^5$，$\mid a_i\mid \le 10^5\backslash left|\; a\_i\; \backslash right|\; \backslash le\; 10^5$。

分析 $f_i(x)f\_i(x)$ 的性质，由于 $\arctan \backslash arctan$ 函数在 $\mathbb{R}\backslash mathbb\{R\}$ 上单调递增，且有 ，那么只需要最小化 $\mid k_i\sec (x-a_i)\mid \backslash left|\; k\_i\backslash sec(x-a\_i)\; \backslash right|$，取倒数之后就是最大化 $\mid \frac{\cos (x-a_i)}{k_i}\mid \backslash left|\backslash frac\{\backslash cos(x-a\_i)\}\{k\_i\}\; \backslash right|$，去掉绝对值之后就是最大化 $\frac{\cos (x-a_i)}{k_i}\backslash frac\{\backslash cos(x-a\_i)\}\{k\_i\}$ 或其相反数。

注意到 $\frac{\cos (x-a_i)}{k_i}=\frac{\cos (x)\cos (a_i)+\sin (x)\sin (a_i)}{k_i}=(\cos (x),\sin (x))\cdot (\frac{\cos (a_i)}{k_i},\frac{\sin (a_i)}{k_i})\backslash frac\{\backslash cos(x-a\_i)\}\{k\_i\}\; =\; \backslash frac\{\backslash cos(x)\backslash cos(a\_i)+\backslash sin(x)\backslash sin(a\_i)\}\{k\_i\}=(\backslash cos(x),\backslash sin(x))\backslash cdot\; (\backslash frac\{\backslash cos(a\_i)\}\{k\_i\},\backslash frac\{\backslash sin(a\_i)\}\{k\_i\})$，也就是要存在某个方向 $(\cos (x),\sin (x))(\backslash cos(x),\backslash sin(x))$ 使得 $(\frac{\cos (a_i)}{k_i},\frac{\sin (a_i)}{k_i})(\backslash frac\{\backslash cos(a\_i)\}\{k\_i\},\backslash frac\{\backslash sin(a\_i)\}\{k\_i\})$ 在这个方向上的投影最大，这意味着这个点要在所有 $(\frac{\cos (a_i)}{k_i},\frac{\sin (a_i)}{k_i})(\backslash frac\{\backslash cos(a\_i)\}\{k\_i\},\backslash frac\{\backslash sin(a\_i)\}\{k\_i\})$ 和 $(-\frac{\cos (a_i)}{k_i},-\frac{\sin (a_i)}{k_i})(-\backslash frac\{\backslash cos(a\_i)\}\{k\_i\},-\backslash frac\{\backslash sin(a\_i)\}\{k\_i\})$ 这 $2n2n$ 个点构成的点集的凸包上。使用任意凸包算法求解这 $2n2n$ 个点的凸包，所有凸包上的点对应的 $ii$ 都存在 $x_{i}x\_i$ 使得 $f_i(x_i)f\_i(x\_i)$ 是所有 $f_1(x_i),f_2(x_i),\cdots ,f_n(x_i)f\_1(x\_i),f\_2(x\_i),\backslash cdots,f\_n(x\_i)$ 之中的严格最小值。

这里还有一个问题是如何选取浮点数比较的容错值 $ϵ\backslash epsilon$，实测选取 $ϵ=10^{-30}\backslash epsilon\; =\; 10^\{-30\}$ 可以通过此题，但是如果在赛中去对各种 $ϵ\backslash epsilon$ 进行尝试，很容易产生大量罚时从而影响成绩。

参考代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=49719670