文章

1

粉丝

227

获赞

1

访问

1.2k

头像
题目的数据不大,可以通过暴力枚举来通过
P1620
发布于2023年3月31日 16:44
阅读数 1.2k

题目的意思是相当于在点集中找到一个面积最小的三角形,因为面积最小要大于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...

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发