暴力法解决最近对问题和凸包问题-实现可视化

2024-05-10 22:20

本文主要是介绍暴力法解决最近对问题和凸包问题-实现可视化,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

最近对问题

凸包问题


最近对问题

顾名思义就是采用蛮力法求出所有点之间的距离,然后进行比较找出第一个最近对,一个一个进行比较。

大概思路就是如图(每个圈代表一个数对)

第一个和其他四个比较

第二个和其他三个比较

.......

最后比较最小的

image-20240510191434898

代码

图形化界面主要是easyx的graphics

#include<iostream>
#include <fstream>
#include<graphics.h>
#include <conio.h>
using namespace std;
#define Max 20  //20个点的凸包问题
#define maxn 10000
#define time 15
​
typedef struct {int a;int b;
}point;
void draw_point(point x[]);
void draw_line(int a, int b, int c, int d);
void judge(point x[]);
​
int main() {point x[Max];
​ifstream in("a.txt");cout << "从txt中读取点坐标如下:" << endl;for (int i = 0; i < 20; i++){in >> x[i].a;in >> x[i].b;}for (int i = 0; i < 20; i++){cout << i + 1 << ":" << "(" << x[i].a << "," << x[i].b << ")" << endl;}cout << endl << endl;in.close();cout << "存储的数据如下:" << endl;draw_point(x);judge(x);getchar();return 0;
}
​
void judge(point x[]) {int i, j, a, b, c, n, num1 = 0, num2 = 0;int flag;for (i = 0; i < Max; i++){for (j = i + 1; j < Max; j++){b = x[i].a - x[j].a;a = x[j].b - x[i].b;c = x[i].a * x[j].b - x[j].a * x[i].b;
​for (n = 0; n < Max; n++){if (n != i && n != j){flag = x[n].a * a + x[n].b * b;if (flag < c)num1++;else if (flag > c)num2++;else {num1++;num2++;};}}if (num1 == 18 || num2 == 18){cout << "如下两点是极边:" << "(" << x[i].a << "," << x[i].b << ")" << "(" << x[j].a << "," << x[j].b << ")" << endl;draw_line(x[i].a, x[i].b, x[j].a, x[j].b);}num1 = num2 = 0;}}
​
}
void draw_point(point x[]) {initgraph(880, 680, SHOWCONSOLE);setorigin(320, 240);int a, b;for (int i = 0; i < Max; i++) {a = x[i].a * time;b = x[i].b * time;fillcircle(a, b, 4);}
}
void draw_line(int a, int b, int c, int d)
{line(a * time, b * time, c * time, d * time);
}

运行结果

先写一个a.txt文件的点(20个)

img

运行(可视化界面)

img

凸包问题

凸包问题就是在一个有n个点集的平面上,找出所有的“极点”,这些极点所构成的边界能够把其他所有的点都能包含在内。

思路

由两个点连起来的直线会将平面分成两部分,其中半个平面的点都满足ax+by>c ,另一半平面中的点都满足ax+by<c ,对于线上的点来说满足ax+by=c。因此,算法的思路就是对于每个点带入ax+by-c,判断表达式结果的符号是否相同即可。

代码

#include<iostream>
#include<fstream>
#include<graphics.h>
#include<cmath>
#include<algorithm>
using namespace std;
​
#define Max 20 // 最大点数
#define maxn 10000
#define time 15
​
typedef struct {int a;int b;
} point;
​
void draw_point(point x[]);
void draw_line(int a, int b, int c, int d);
void closest_pair(point x[]);
​
int main() {point x[Max];
​
ifstream in("points.txt"); 
cout << "从txt文件中读取点坐标:" << endl;for (int i = 0; i < Max; i++) {in >> x[i].a;in >> x[i].b;}for (int i = 0; i < Max; i++) {cout << i + 1 << ": (" << x[i].a << ", " << x[i].b << ")" << endl;}cout << endl << endl;in.close();
​cout << "存储的数据如下:" << endl;draw_point(x);closest_pair(x);getchar();closegraph(); // 关闭图形窗口return 0;
}
​
void closest_pair(point x[]) {int min_distance = INT_MAX;int pair1 = -1, pair2 = -1;
​for (int i = 0; i < Max; i++) {for (int j = i + 1; j < Max; j++) {int distance = pow(x[i].a - x[j].a, 2) + pow(x[i].b - x[j].b, 2);if (distance < min_distance) {min_distance = distance;pair1 = i;pair2 = j;}}}
​cout << "最近的点对:" << endl;cout << "(" << x[pair1].a << ", " << x[pair1].b << ") 和 (" << x[pair2].a << ", " << x[pair2].b << ")" << endl;
​// 绘制最近的点对连线draw_line(x[pair1].a, x[pair1].b, x[pair2].a, x[pair2].b);
}
​
void draw_point(point x[]) {initgraph(880, 680, SHOWCONSOLE);setorigin(320, 240);int a, b;for (int i = 0; i < Max; i++) {a = x[i].a * time;b = x[i].b * time;fillcircle(a, b, 4);}
}
​
void draw_line(int a, int b, int c, int d) {line(a * time, b * time, c * time, d * time);
}

运行结果

先写一个points.txt文件的点(20个)

img

运行:(可视化界面)

这篇关于暴力法解决最近对问题和凸包问题-实现可视化的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/977715

相关文章

pandas中位数填充空值的实现示例

《pandas中位数填充空值的实现示例》中位数填充是一种简单而有效的方法,用于填充数据集中缺失的值,本文就来介绍一下pandas中位数填充空值的实现,具有一定的参考价值,感兴趣的可以了解一下... 目录什么是中位数填充?为什么选择中位数填充?示例数据结果分析完整代码总结在数据分析和机器学习过程中,处理缺失数

Golang HashMap实现原理解析

《GolangHashMap实现原理解析》HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持高效的插入、查找和删除操作,:本文主要介绍GolangH... 目录HashMap是一种基于哈希表实现的键值对存储结构,它通过哈希函数将键映射到数组的索引位置,支持

Pandas使用AdaBoost进行分类的实现

《Pandas使用AdaBoost进行分类的实现》Pandas和AdaBoost分类算法,可以高效地进行数据预处理和分类任务,本文主要介绍了Pandas使用AdaBoost进行分类的实现,具有一定的参... 目录什么是 AdaBoost?使用 AdaBoost 的步骤安装必要的库步骤一:数据准备步骤二:模型

Spring Boot中JSON数值溢出问题从报错到优雅解决办法

《SpringBoot中JSON数值溢出问题从报错到优雅解决办法》:本文主要介绍SpringBoot中JSON数值溢出问题从报错到优雅的解决办法,通过修改字段类型为Long、添加全局异常处理和... 目录一、问题背景:为什么我的接口突然报错了?二、为什么会发生这个错误?1. Java 数据类型的“容量”限制

使用Pandas进行均值填充的实现

《使用Pandas进行均值填充的实现》缺失数据(NaN值)是一个常见的问题,我们可以通过多种方法来处理缺失数据,其中一种常用的方法是均值填充,本文主要介绍了使用Pandas进行均值填充的实现,感兴趣的... 目录什么是均值填充?为什么选择均值填充?均值填充的步骤实际代码示例总结在数据分析和处理过程中,缺失数

Java对象转换的实现方式汇总

《Java对象转换的实现方式汇总》:本文主要介绍Java对象转换的多种实现方式,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录Java对象转换的多种实现方式1. 手动映射(Manual Mapping)2. Builder模式3. 工具类辅助映

Go语言开发实现查询IP信息的MCP服务器

《Go语言开发实现查询IP信息的MCP服务器》随着MCP的快速普及和广泛应用,MCP服务器也层出不穷,本文将详细介绍如何在Go语言中使用go-mcp库来开发一个查询IP信息的MCP... 目录前言mcp-ip-geo 服务器目录结构说明查询 IP 信息功能实现工具实现工具管理查询单个 IP 信息工具的实现服

SpringBoot基于配置实现短信服务策略的动态切换

《SpringBoot基于配置实现短信服务策略的动态切换》这篇文章主要为大家详细介绍了SpringBoot在接入多个短信服务商(如阿里云、腾讯云、华为云)后,如何根据配置或环境切换使用不同的服务商,需... 目录目标功能示例配置(application.yml)配置类绑定短信发送策略接口示例:阿里云 & 腾

关于MongoDB图片URL存储异常问题以及解决

《关于MongoDB图片URL存储异常问题以及解决》:本文主要介绍关于MongoDB图片URL存储异常问题以及解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐... 目录MongoDB图片URL存储异常问题项目场景问题描述原因分析解决方案预防措施js总结MongoDB图

SpringBoot项目中报错The field screenShot exceeds its maximum permitted size of 1048576 bytes.的问题及解决

《SpringBoot项目中报错ThefieldscreenShotexceedsitsmaximumpermittedsizeof1048576bytes.的问题及解决》这篇文章... 目录项目场景问题描述原因分析解决方案总结项目场景javascript提示:项目相关背景:项目场景:基于Spring