一开始想用暴力，看了看数据5000，C(5000,3)，大概一万多位数吧。此路不通。
不过还是要暴力。以每个点做原点，构建坐标系，把剩下的点用极角排序后，求相邻两个点之间与该点的面积，在其中取得的最小值即为答案。
这里有一个东西需要证明，只取相邻两点作三角形的话是否包含了所有可以构造的三角形。比如六个点，构成一个六边形，如果只取相邻边就会漏掉一些三角形。不过好在可以证明这些三角形一定会比我们取的三角形面积小。我也不确定我的证明过程是否正确，希望有兴趣的大佬可以和我交流一下。我就不贴自己的证明过程了太懒了
#include<bits/stdc++.h> #define maxn 5005 #define INF 0x3f3f3f3f using namespace std; typedef long long ll; struct point { ll x,y; }p[maxn],t[maxn]; ll min(ll a,ll b) { return a<b; } bool cmp(point a,point b) { return a.x*b.y<a.y*b.x; } double area(point a,point b) { return abs(a.x*b.y-a.y*b.x); } int main() { int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%lld%lld",&p[i].x,&p[i].y); ll minn=INF; for(int i=0;i<n;i++) { int k=0; for(int j=0;j<n;j++) { if(i==j) continue; t[k].x=p[j].x-p[i].x; t[k].y=p[j].y-p[i].y; k++; } sort(t,t+k,cmp); for(int j=1;j<k;j++) minn=min(minn,area(t[j],t[j-1])); } printf("%.3f\n",minn/2.0); return 0; }
原文：https://www.cnblogs.com/FTA-Macro/p/10466538.html
