L3-021 神坛

女爷i 2023-09-26 18:27 3阅读 0赞

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

#### 样例解释 ####

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

![983e762945d18be36e11d0392acd3125.jpeg][]

当你不会时：请记住**最简单粗暴**的方法（暴力版）![e69e86f5048245ee87729d2832c79d99.png][]

![59ace4513d574e948b56130f95a4fdb9.png][]

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

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

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

![6509cbf26dd64f6cb9b9f0e935da8665.png][]

![e2cc4a967d894d21828979de590a0111.png][]

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

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

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

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

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

![c90dccc1f4874590b4b1fa9da4ff608e.png][]

![03bb8657e5fb4cab94ef5f481c43fbd4.png][]

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

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

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

![5a75d1c7a3be472081af2652d184035a.png][]

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

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

![4ff74374a8104d2b82ca0d8c9805a6d0.png][]

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

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

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

![54ae3dad2bb64e9dba7b937845a49c0a.png][]

![28e3fba503f04029aec7a637c18ff357.png][]

完整源代码：

#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;		
    }

[983e762945d18be36e11d0392acd3125.jpeg]: https://img-blog.csdnimg.cn/img_convert/983e762945d18be36e11d0392acd3125.jpeg
[e69e86f5048245ee87729d2832c79d99.png]: https://img-blog.csdnimg.cn/e69e86f5048245ee87729d2832c79d99.png
[59ace4513d574e948b56130f95a4fdb9.png]: https://img-blog.csdnimg.cn/59ace4513d574e948b56130f95a4fdb9.png
[6509cbf26dd64f6cb9b9f0e935da8665.png]: https://img-blog.csdnimg.cn/6509cbf26dd64f6cb9b9f0e935da8665.png
[e2cc4a967d894d21828979de590a0111.png]: https://img-blog.csdnimg.cn/e2cc4a967d894d21828979de590a0111.png
[c90dccc1f4874590b4b1fa9da4ff608e.png]: https://img-blog.csdnimg.cn/c90dccc1f4874590b4b1fa9da4ff608e.png
[03bb8657e5fb4cab94ef5f481c43fbd4.png]: https://img-blog.csdnimg.cn/03bb8657e5fb4cab94ef5f481c43fbd4.png
[5a75d1c7a3be472081af2652d184035a.png]: https://img-blog.csdnimg.cn/5a75d1c7a3be472081af2652d184035a.png
[4ff74374a8104d2b82ca0d8c9805a6d0.png]: https://img-blog.csdnimg.cn/4ff74374a8104d2b82ca0d8c9805a6d0.png
[54ae3dad2bb64e9dba7b937845a49c0a.png]: https://img-blog.csdnimg.cn/54ae3dad2bb64e9dba7b937845a49c0a.png
[28e3fba503f04029aec7a637c18ff357.png]: https://img-blog.csdnimg.cn/28e3fba503f04029aec7a637c18ff357.png