题目要求
在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为 0.000。
长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。
输入格式：
输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n 行，每行有两个整数，分别表示神石的横坐标、纵坐标（−109≤ 横坐标、纵坐标 <109）。
输出格式：
在一行中输出神坛的最小面积，四舍五入保留 3 位小数。
输入样例：
8
3 4
2 4
1 1
4 1
0 3
3 0
1 3
4 2
输出样例：
0.500
样例解释：
输出的数值等于图中红色或紫色框线的三角形的面积。
解题前提及思路
该程序可归类为计算平面内点集的最小面积的凸包
凹包算法
概念
定义：对于平面内的一组点，凸包是指这组点的凸多边形中，所有的顶点都是这组点中的点的集合。
凸包（Convex Hull）算法是一种计算二维平面点集最小凸多边形的算法。而凸多边形具有如下特征：在其内部的任意两点，连线都必须位于多边形内部。
因此，凹包（Concave Hull）问题就是将给定的点集包围在一个凹多边形中的算法。凹包问题的难点在于如何确定多边形的形状和顶点，目前已经存在一些解决方案，包括基于 alpha 型和 beta 型形态学的方法、基于分割重组的方法、基于斯蒂尔-沃森（Stiel-Watson）统计的方法等等。
步骤
先求出每个点的单位向量，根据单位向量在极坐标系下的极角从小到大排序，然后按照排序后的顺序依次加入点，如果当前点不是凸包上的点，则一直弹掉栈顶元素直到满足要求，最后栈内存储的就是凸包上所有的点了。
解题思路
用结构体存储平面内的点的坐标及其单位向量，以及该点的编号。
求出每个点的单位向量，并根据该向量的极角从小到大排序。
遍历排序后的点集，依次判断每个点是否在凸包上。如果是，将其入栈；否则，弹出栈顶元素直到满足凸包条件。
最后栈内存储的即为凸包上所有的点的编号。
根据这些点的坐标计算凸包的面积，具体方法是用两个相邻点和原点组成的三角形面积求和。
代码
#include<iostream> #include<algorithm> #include<cmath> using namespace std; struct node { long long x, y; // 存储平面内的点的坐标 int xiang; // 存储所在象限 }; int n; bool cmp(node x,node y) { // 判断两个点所在象限是否相同 if(x.xiang != y.xiang) return x.xiang < y.xiang; // 如果所在象限相同，则判断它们组成的向量与 x 轴之间的夹角大小来排序， // 如果向量之间的叉积为正数，表明顺时针旋转需要交换两个向量的位置，这时 // 我们认为前一个向量更小；如果叉积为负数，表明逆时针旋转不需要交换，这时 // 认为后一个向量更小。 return x.x * y.y - x.y * y.x < 0; } // 判断点所在象限的函数 int judge(node x) { if(x.x > 0 && x.y > 0) return 1; if(x.x < 0 && x.y > 0) return 2; if(x.x < 0 && x.y < 0) return 3; if(x.x > 0 && x.y < 0) return 4; } int main() { cin >> n; struct node a[5010], b[5010]; for(int i = 1; i <= n; i++) { cin >> a[i].x >> a[i].y; } double s = -1; int cnt; for(int i = 1; i <= n; i++) { cnt = 1; for(int j = 1; j <= n; j++) { if(i == j) continue; b[cnt].x = a[j].x - a[i].x; b[cnt].y = a[j].y - a[i].y; b[cnt].xiang = judge(b[cnt]); cnt++; } sort(b + 1, b + n, cmp); // 排序 for(int j = 1; j < n - 1; j++) { // 计算三角形面积，求最小值 if(s == -1 || fabs(b[j + 1].x * b[j].y - b[j + 1].y * b[j].x) * 0.5 < s) s = fabs(b[j + 1].x * b[j].y - b[j + 1].y * b[j].x) * 0.5; } } printf("%.3f\n", s); return 0; } }
需要注意的是，在计算向量的极角时，可以用 atan2(y, x) 函数，而不是简单地使用 arctan(y/x)，这是因为 atan2 函数会根据 y 和 x 的符号自动确定向量在哪个象限，避免了分段计算的麻烦。
tan(y/x)及tan2(y,x)函数
tan(y, x) 函数表示求以 (x, y) 为起点的射线与 x 轴正方向之间的夹角的正切值。在求解过程中，需要使用参数 y 和 x 分别代表这条射线在 y 方向和 x 方向上的长度。因此，tan 函数的返回值是一个实数类型。
而 atan2(y, x) 函数则是求以原点为起点的射线与 x 轴之间的夹角，其输入参数也是射线在 y 和 x 方向上的长度。需要注意的是，atan2(y, x) 函数返回值的单位是弧度制，通常需要进行转换后才能得到以角度为单位的值。
atan2(y, x) 函数在计算以原点为起点的向量与 x 轴正方向所夹角度数时，会根据向量在平面上的位置自动确定向量所在的象限。
具体来说，如果向量位于第一象限，即其x和y坐标均为正数，
那么atan2(y, x)计算出的角度值将是 0 到 π/2 之间的一个正值。
如果向量位于第二象限，即其x坐标为负数，而y坐标为正数，
那么atan2(y, x)计算出的角度值将是 π/2 到 π 之间的一个正值。
另外，由于 tan(y, x) 中需要除以 x 的值，所以当 x 的值为 0 时会导致除数为 0 的错误。而 atan2(y, x) 可以避免这种错误的发生，因此更加常用。
总结
本文使用凹包算法、atan2(y,x)函数进行解题，读者可躬身实践。
我是秋说，我们下次见。
