星图（Easy Ver.）

给定二维平面上不同的 $n$ 个点 $S=\left\{(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)\right\}$，保证任意两点的连线不平行于坐标轴. 称 $\triangle ABC$ 是好三角形，当且仅当其三边均不平行于坐标轴，且不存在 $A,B,C$ 的一个排列 $P,Q,R$，使得 $x_Py_Q>y_R$. 称一个由 $S$ 中元素为顶点的三角形构成的集合 $T$ 是一个好三角剖分，当且仅当这些三角形都是好三角形，且它们的内部两两不交.

请求出好三角剖分大小的最大可能值，并给出一个构造.

$3\le n\le 5\times 10^5, |x_i|,|y_i|\le 10^9$.

Expected Difficulty: Easy

题解

tag: 构造，单调栈

考察三角剖分对应的平面图，设其最外圈的点数为 $x$，三角剖分的大小为 $t$. 由平面图欧拉公式得 $V+F-E=1$，又由 $F\ge t, E= \dfrac{3F+x}2$ 得 $t\le F=2(n-1)-x$. 于是问题转化为最小化这个 $x$ 并顺手取到等号.

来看哪些点一定会出现在最外圈. 肉眼瞪得，当以这点为原点时，若存在某个象限内没有其他点，则该点一定在最外圈. 下面进行构造使得所有等号均成立.

将所有点按纵坐标从小到大排序，依次加入，同时维护两个单调栈 $q_1,q_2$，其中 $x_{q_{1,i}}>x_{q_{1,i-1}},y_{q_{1,i}}>y_{q_{1,i-1}}$；$x_{q_{2,i}}< x_{q_{2,i-1}},y_{q_{2,i}}>y_{q_{2,i-1}}$ 且两栈栈顶元素相同. 当加入点 $(x_i,y_i)$ 时，依次对两栈做如下更新：

若 $q_1$ 不为空，取出 $q_1$ 栈顶元素 $j$，若 $x_i< x_j$，弹栈，且若栈仍非空，取其栈顶 $k$，将 $(i,j,k)$ 加入 $T$. 重复执行这一步直到 $x_i>x_j$；若 $q_2$ 不为空，取出 $q_2$ 栈顶元素 $j$，若 $x_i>x_j$，弹栈，且若栈仍非空，取其栈顶 $k$，将 $(i,j,k)$ 加入 $T$. 重复执行这一步直到 $x_i< x_j$. 容易验证这给出了一个取等.