给定平面内 $n$ 个点，保证横纵坐标互不相同，求能分划为多少个三角形满足三个点都能在同一个矩形上，给出构造方案。

• 首先我会想到一个完全没有任何用处的玩意

  首先这个答案的上界是 $n-2$,小学生都会证明，就是凸多边形三角形划分。

• 我们会自然的考虑去思考如何刻画这个三个点都能在同一个矩形上

  /////此处省略一张图片

  考虑样例解释图2，发现右上角的三个点单调递增，所以我们通过画图后会发现如果三个连续点的 $y_i$ 是单调的，则不能构成，即得到下面结论:

  将所有点按横坐标$x$从小到大排序后，记三个点为$A(x_1,y_1), B(x_2,y_2), C(x_3,y_3)$（满足$x_1充要条件是：

  中间点$B$的纵坐标$y_2$，是三个点纵坐标的严格最大值或严格最小值

下面我们可以有一个很自然的想法是先对于 $x$ 排序，然后考虑继续观察:

我们发现所有的合法的三角形都是个锯齿状的东西，然后我们考虑就是把上锯齿和下锯齿分开讨论。

我们下面以讨论上锯齿为例，下锯齿和上锯齿完全一样:

题目图一省略

我们观察 $P_6$，然后感觉就是和左面比他矮的连边，然后有点类似于旋转，反正相邻的两个三角形共顶点和相邻的边，然后类似于以此逆时针旋转,然后构造就感觉很像栈操作。

下面考虑构造，由于我们已经把这个 $x$ 坐标排好了序，然后考虑每次扫描每个 $x_i$，然后维护一个 $y_i$ 的递增栈，每次就是考虑$x_i，栈顶，栈中第二个$ 的顺序去操作，然后每次弹出栈顶，直到无法形成锯齿状或者栈空了为止。

对于下锯齿的情况完全一致，维护一个递减的栈，这里就不介绍了。