网站建设 有限公司,儿童教育机构网页设计素材,网站和网店的区别,wordpress rockgroup在古老的迈瑞城#xff0c;巍然屹立着 n 块神石。长老们商议#xff0c;选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比#xff0c;因此神坛的面积越小越好。特殊地#xff0c;如果有两块神石坐标相同#xff0c;或者三块神石共线#xff0c;神坛的面积…在古老的迈瑞城巍然屹立着 n 块神石。长老们商议选取 3 块神石围成一个神坛。因为神坛的能量强度与它的面积成反比因此神坛的面积越小越好。特殊地如果有两块神石坐标相同或者三块神石共线神坛的面积为 0.000。
长老们发现这个问题没有那么简单于是委托你编程解决这个难题。
输入格式
输入在第一行给出一个正整数 n3 ≤ 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^9MinArea给小了而且由于有乘法bouble把不够用 上天总是会眷顾努力的人不是吗 相信自己你可以的你能行 完整源代码
#include iostream
#includebits/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.xb.x*a.y;}int main(){int n;scanf(%d,n);for(int i0; in; i)scanf(%lld %lld,p[i].x,p[i].y);//scanf()的效率比cin高 long long MinArea1e18;for(int i0; in; i){Point sides[n]; //每个点都能和其他n-1个点组成n-1条向量边 int k0;for(int j0; jn; j){if(ij) continue; sides[k] {p[j].x-p[i].x , p[j].y-p[i].y};//向量边 p[j]-p[i] }sort(sides,sidesk,cmp);for(int j1; jk; 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;
}
