文章
1
粉丝
227
获赞
1
访问
1.5k
题目的意思是相当于在点集中找到一个面积最小的三角形,因为面积最小要大于0,所以三点共线的情况要排除掉。
此类题目的难点应该是如何用复杂度更低的做法求出答案,因此我一开始的方向是寻找一个复杂度比n^3更低的做法,结果我发现的确是有这样的算法,但是也很难,对于我这样的编程小白来说去写这样的算法更为耗时,在观察了这道题目的数据之后我选择了暴力枚举,学有余力的同学可以去百度这个算法自己试着实现,这里有一个b站的视频用可视化的方法阐述了算法,我觉得比起文字更好的让人理解了。https://www.bilibili.com/video/BV1s54y1b7UL/?spm_id_from=333.1007.top_right_bar_window_default_collection.content.click&vd_source=d44d27318192d20e799ea9424e8f4e6a
下面贴出我暴力枚举的算法,ps:题目输出的不可能需要改成英文,不然无法ac
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
double area;
struct point{
double x,y;
};
point a[105];
double Area(int p1, int p2, int p3){
return 0.5*fabs((a[p2].x -a[p1].x )*(a[p3].y - a[p2].y ) - (a[p3].x - a[p2].x )*(a[p2].y - a[p1].y ));
}
int main(){
int T,n;
cin>>T;
while(T--){
cin>>n;
for(int i=0...
登录后发布评论
暂无评论,来抢沙发