L3-021 神坛

在古老的迈瑞城，巍然屹立着 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

样例解释

输出的数值等于图中红色或紫色框线的三角形的面积。

当你不会时：请记住最简单粗暴的方法（暴力版）

分析原因：是哪超时了呢，是因为什么超时的

得到结论：第三层for循环时，大部分时间都在进行无效的重复计算

大胆尝试：有没有什么办法可以让它不重复或者少重复呢

很不幸，还是如此，并没有得到跟多的分数，怎么办

--》时间不够，那就只能放弃了

--》还有时间，我能行，我可以的，我一定行

总结：三层循环嵌套肯定是不行了，我已经进全力优化了，到达极限了，不行啊。

极限分析：既然三层不行，那两层能不能实现呢，多写几个第二层的循环代替第三层行不行呢，试试？？？！！！

分析：很不错，又混了两分，目的达到了，超时问题已解决，接下来再试试能不能解决答案错误问题。为什么错了呢？？？？？？？？？？？？？？

结论：原来是因为 不相邻的两条边组成的三角形也可能比相邻的要小。

再想想办法，马上就要出来了。

//高数下第八章知识   向量的外积   =    |a||b|sin <a,b>

//        而三角形的面积公式    S   =1/2 |a||b|sin <a,b>

      

没注意横纵坐标范围（+10^9），MinArea给小了，而且由于有乘法，bouble把不够用

上天总是会眷顾努力的人，不是吗

相信自己，你可以的，你能行

完整源代码：

#include <iostream>
#include<bits/stdc++.h>
#include <cmath>
using namespace std;struct Point{long long x;//x坐标long long y;//y坐标
}p[5001];bool cmp(Point a,Point b){//按顺时针排序return b.y*a.x>b.x*a.y;}int main(){int n;scanf("%d",&n);for(int i=0; i<n; i++)scanf("%lld %lld",&p[i].x,&p[i].y);//scanf()的效率比cin高 long long MinArea=1e18;for(int i=0; i<n; i++){Point sides[n]; //每个点都能和其他n-1个点组成n-1条向量边 int k=0;for(int j=0; j<n; j++){if(i==j) continue;	sides[k++] = {p[j].x-p[i].x , p[j].y-p[i].y};//向量边  p[j]-p[i] }sort(sides,sides+k,cmp);for(int j=1; j<k; j++){  //这是嵌套在第一层里面的第二循环，而不是嵌套在第二层里面的第三层循环	//三角形向量面积公式 S = 1/2 * | xA*yB - xB*yA |MinArea = min(MinArea,abs(sides[j].x*sides[j-1].y - sides[j-1].x*sides[j].y)); }			} printf("%.3f",MinArea/2.0);		return 0;		
}