纯小白蓝桥杯备赛笔记--DAY14（计算几何）

文章目录

    • 计算几何基础
      • 平面几何距离
      • 圆的周长和面积
      • 圆与圆之间的关系：
      • 海伦公式计算三角形面积
      • 点到直线的距离
    • 点积和叉积
      • 例题：
    • 点和线的关系
      • 点的表示形式和代码
      • 判断点在直线的那边
      • 点到线的垂足
      • 点到线的距离
      • 例题-1242
      • 例题-1240
      • 升级--点到线段的距离--1285
    • 任意多边形面积的计算
      • 平面向量
      • 向量积
      • 求任意多边形的面积：
    • 二维计算几何基础

计算几何基础

平面几何距离

在这里插入图片描述

  • 曼哈顿距离：
int dist(int x1,int y1,int x2,int y2)
{
	int dx=abs(x1-x2);
	int dy=abs(y1-y2);
	return dx+dy;
}
  • 欧几里得距离：
double dist(double x1,double y1,double x2,double y2)
{
	double dx=x1-x2;
	double dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
}

其中，pow函数是比较慢的，这里没有必要使用。

圆的周长和面积

在这里插入图片描述

圆与圆之间的关系：

在这里插入图片描述

海伦公式计算三角形面积

在这里插入图片描述

点到直线的距离

在这里插入图片描述

  • 那么向量如何求解这个问题：
    在这里插入图片描述
  • 例题：1286
#include<bits/stdc++.h>
using namespace std;
//求距离
double dist(double x1,double y1,double x2,double y2)
{
	double dx=x1-x2,dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
 } 
void solve()
{
	double xa,ya,xb,yb,xc,yc;cin>>xa>>ya>>xb>>yb>>xc>>yc;
	//把向量处理出来，ca，cb
	 double xca=xa-xc,yca=ya-yc;
	 double xcb=xb-xc,ycb=yb-yc;
	 //叉乘 
	 double ans=abs(xca*ycb-xcb*yca)/dist(xa,ya,xb,yb);
	 cout<<fixed<<setprecision(2)<<ans<<endl; 
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int i;cin>>i;
	while(i--)solve();
	return 0;
}
  • 总结：
  1. 封装函数，按照输入的组别来处理。
  2. 在这个函数中处理出两条边叉乘的结果。
  3. 最终的结果是叉乘结果的绝对值除以两者之间的距离。
  4. 求距离再次封装一个函数:使用欧几里得算法。
  5. 注意使用double类型以及保留小数位数。
  • 例题：求三角形面积–1231
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
//求距离
double dist(double x1,double y1,double x2,double y2)
{
	double dx=x1-x2,dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
 } 
void solve()
{
	double x1,y1,x2,y2,x3,y3;cin>>x1>>y1>>x2>>y2>>x3>>y3;
	long double a=dist(x1,y1,x2,y2);
	long double b=dist(x1,y1,x3,y3);
	long double c=dist(x2,y2,x3,y3);//开了一次根号，再求一次根号很容易导致精度误差 
	long double p=(a+b+c)/2;
	long double ans=sqrt(p*(p-a)*(p-b)*(p-c));
	cout<<fixed<<setprecision(2)<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int i;cin>>i;
	while(i--)solve();
	return 0;
}

点积和叉积

  • 概念：
    在这里插入图片描述
  • 点积的代码实现：
#include<bits/stdc++.h>
using namespace std;

struct Point{//定义点的结构体 
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
	Point operator+(Point  p){return Point(x+p.x,y+p.y);}
	Point operator-(Point  p){return Point(x-p.x,y-p.y);}
	Point operator*(double a){return Point(x*a,y*a);}
	Point operator/(double a){return Point(x/a,y/a);}
	Point operator*(Point  p){return Point(x*p.x+y*p.y);}//点积 
	
}; 
typedef Point Vector;
int main()
{
	Vector a(1.0,3.0);
	Vector b(2.0,4.0);
	double dot_product=a*b;//使用重载的*运算符计算点积
	cout<<dot_product<<endl;
	return 0; 
  }
  • 叉积在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述
  • 代码实现：
#include<bits/stdc++.h>
using namespace std;

struct Point{//定义点的结构体 
	double x,y;
	Point(){}
	Point(double x,double y):x(x),y(y){}
//乘法 
	Point operator*(double a){return Point(x*a,y*a);}
//点乘 
	Point operator*(Point  p){return Point(x*p.x+y*p.y);}//点积 
	double cross(const Point &p)const{return x*p.y-y*p.x;} 
	
}; 
typedef Point Vector;
int main()
{
	Vector a(1.0,3.0);
	Vector b(2.0,4.0);
	double dot_product=a*b;//使用重载的*运算符计算点积
	cout<<dot_product<<endl;
	double cross_product=a.cross(b);
	cout<<cross_product<<endl;
	return 0; 
  }

例题：

在这里插入图片描述

  • 怎么判断两条边是否垂直呢？
    点积为0即可。
#include<bits/stdc++.h>
using namespace std;

struct Point{//定义点的结构体 
	double x,y;
	Point():x(0),y(0) {} //初始化 
	//两点相减，得到向量
	double operator-(const Point &p)const{return x-p.x,y-p.y};
	Point(double x,double y):x(x),y(y){}
//点积
    double dot(const Point &p)const{return x*p.x-y*p.y;}  
//	判断当前的向量和另一向量是否垂直
	bool ischui(const Point &p)const{
	return fabs(dot(p))<1e-10;//点积为0即垂直 
	} 
}; 

int main()
{
	int n,k,count=0;
	cin>>n>>k;
	for(int i=0;i<n;i++){
		Point start,turn,end;
		cin>>start.x>>start.y;
		cin>>turn.x>>turn.y;
		cin>>end.x>>end.y;
//		计算两个向量
		Point v1=turn-start;
		Point v2=end-turn;
//		检查是否垂直
		if(ischui(v2)){
			count++;
		} 
//		计算上取整
		int result=(count+k-1)/k;
		cout<<result<<end;
		return 0; 
	} 
  }

点和线的关系

点的表示形式和代码

//使用pair存储
using Point =pair<int,int>;
//使用结构体
struct Point{
	int x,y;
};

判断点在直线的那边

在这里插入图片描述

点到线的垂足

在这里插入图片描述

点到线的距离

在这里插入图片描述

例题-1242

#include<bits/stdc++.h>
using namespace std;
struct Point{
	double x;
	double y;
};
inline double cross(const Point& p1,const Point& p2)
{
	return p1.x*p2.y-p2.x*p1.y;
}
int main()
{
	int n;
	Point p1,p2,p3;
	cin>>n;
	while(n--)
	{
		cin>>p1.x>>p1.y>>p2.x>>p2.y>>p3.x>>p3.y;
		cout<<(cross(p1,p2)+cross(p2,p3)+cross(p1,p3)==0?"Yes":"No")<<endl;
		
	}
	return 0;
}

inline表示建议编译器将cross函数的实现直接插入到调用它的地方，以提高性能。

例题-1240

#include <bits/stdc++.h>
using namespace std;

void solve(){
  double xa,ya,xb,yb,xc,yc;
  cin>>xa>>ya>>xb>>yb>>xc>>yc;
  double xAB=xb-xa,yAB=yb-ya;
  double xBC=xb-xc,yBC=yb-yc;
  double p=xAB*yBC-xBC*yAB;
  if(p==0){
    cout<<"IN"<<"\n";
  }
  else if(p>0){
    cout<<"R"<<"\n";
  }
  else{
    cout<<"L"<<"\n";
  }
}

int main()
{
  int t;cin>>t;
  while(t--)solve();
  
  return 0;
}

总结：遇到直线用向量比较好。

升级–点到线段的距离–1285

？：这时候还能不能做垂线呢？
能。且点到直线的距离有一个垂足，判断垂足是否在线段AB内。
在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;

double dist(double x1,double y1,double x2,double y2){
  double dx=x1-x2,dy=y1-y2;
  return sqrt(dx*dx+dy*dy);
}


int main()
{
  ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
  int t;cin>>t;
  while(t--){
    double xa,ya,xb,yb,xc,yc;
    cin>>xa>>ya>>xb>>yb>>xc>>yc;
    if((yb-ya)/(xb-xa)!=(yc-yb)/(xc-xb)){
    double xCA=xa-xc,yCA=ya-yc;
    double xCB=xb-xc,yCB=yb-yc;
    double ans=abs(xCA*yCB-xCB*yCA)/dist(xa,ya,xb,yb);
    cout<<fixed<<setprecision(2)<<ans<<"\n";
    }
    else{
      double d1=dist(xa,ya,xc,yc);
      double d2=dist(xb,yb,xc,yc);
      cout<<fixed<<setprecision(2)<<min(d1,d2)<<"\n";
    }

  }
  return 0;
}
  • 题解逻辑;
  • 当斜率不相等时，利用点到直线的距离公式求距离。
  • 当斜率相等时，也就是说c在直线AB上，求ca和cb的最小值。

任意多边形面积的计算

平面向量

在这里插入图片描述
在这里插入图片描述

向量积

  • 内积：在这里插入图片描述
  • 外积：在这里插入图片描述

求任意多边形的面积：

在这里插入图片描述

  • 求三角形的面积
#include<bits/stdc++.h>
using namespace std;
using ll =long long;
//求距离
double dist(double x1,double y1,double x2,double y2)
{
	double dx=x1-x2,dy=y1-y2;
	return sqrt(dx*dx+dy*dy);
 } 
void solve()
{
	double x1,y1,x2,y2,x3,y3;cin>>x1>>y1>>x2>>y2>>x3>>y3;
	long double a=dist(x1,y1,x2,y2);
	long double b=dist(x1,y1,x3,y3);
	long double c=dist(x2,y2,x3,y3);//开了一次根号，再求一次根号很容易导致精度误差 
	long double p=(a+b+c)/2;
	long double ans=sqrt(p*(p-a)*(p-b)*(p-c));
	cout<<fixed<<setprecision(2)<<ans<<endl;
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	int i;cin>>i;
	while(i--)solve();
	return 0;
}

二维计算几何基础

参考文献

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/535657.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

指定世界TOP名校|医学研究学者公派美国麻省理工学院做博士后

指定世界TOP名校|医学研究学者公派美国麻省理工学院做博士后

W医生公派博士后条件为&#xff1a;世界TOP100的知名高校&#xff0c;研究方向相符且前沿。最终我们用世界顶级高校-美国麻省理工学院&#xff08;MIT&#xff09;的博士后邀请函助其获得单位资助&#xff0c;顺利通过签证并出国。 W医生背景&#xff1a; 申请类型&#xff1a…
阅读更多...
LC 501.二叉搜索树中的众数

LC 501.二叉搜索树中的众数

501.二叉搜索树中的众数 给你一个含重复值的二叉搜索树&#xff08;BST&#xff09;的根节点 root &#xff0c;找出并返回 BST 中的所有 众数&#xff08;即&#xff0c;出现频率最高的元素&#xff09;。 如果树中有不止一个众数&#xff0c;可以按 任意顺序 返回。 假定 …
阅读更多...
全国贫困县DID数据（2008-2022年）

全国贫困县DID数据（2008-2022年）

数据来源&#xff1a;国W院扶贫开发领导小组办公室 时间跨度&#xff1a;2008-2022年 数据范围&#xff1a;各县域 数据指标 年份 县域名称 所属地市 所属省份 县域代码 是否贫困县(是为1&#xff0c;否为0) 参考文献&#xff1a; [1]马雯嘉,吴茂祯.从全面脱贫到乡村振兴…
阅读更多...
VQ-BeT: Behavior Generation with Latent Actions 代码复现(Mujoco 安装)

VQ-BeT: Behavior Generation with Latent Actions 代码复现(Mujoco 安装)

代码地址&#xff1a;https://github.com/jayLEE0301/vq_bet_official.git 创建环境 conda create -n vq-bet python3.9 conda activate vq-bet拉取库 git clone https://github.com/jayLEE0301/vq_bet_official.git export PROJ_ROOT$(pwd)安装pytorch conda install pyto…
阅读更多...
AI论文速读 | 线性时间序列预测模型分析

AI论文速读 | 线性时间序列预测模型分析

论文标题&#xff1a;An Analysis of Linear Time Series Forecasting Models 作者&#xff1a; William Toner&#xff0c; Luke Darlow 机构&#xff1a;爱丁堡大学&#xff08;Edinburgh&#xff09;&#xff0c;华为研究中心&#xff08;爱丁堡&#xff09; 论文链接&am…
阅读更多...
开源项目若依放大招了？

开源项目若依放大招了？

前言 鉴于之前写了篇插件式相关的文章&#xff0c;阅读量比起其它文章可不要好太多&#xff0c;所以我决定继续这个主题&#xff01; 以前我们公司用的就是Ruoyi&#xff0c;代码比较简单易懂。但是有些功能确实用不上&#xff0c;比如部门和岗位&#xff0c;每次新项目我拉了…
阅读更多...
Docker安装及开启远程访问

Docker安装及开启远程访问

这几天有人问我docker是怎么开启远程服务的&#xff1f; 正好之前我做过这件事情&#xff0c;并且写了相关的笔记&#xff0c;现在整理为一篇博客发出来。 安装Docker 首先更新一下自己的yum版本 yum update安装一下所需要的软件包 yum-config-manager --add-repo http://…
阅读更多...
Java复习第十七天学习笔记（转发、重定向，GET，POST），附有道云笔记链接

Java复习第十七天学习笔记（转发、重定向，GET，POST），附有道云笔记链接

【有道云笔记】十七 4.3 转发、重定向、Get、POST、乱码 https://note.youdao.com/s/GD5TRksQ 一、转发 转发&#xff1a;一般查询了数据之后&#xff0c;转发到一个jsp页面进行展示 req.setAttribute("list", list); req.getRequestDispatcher("student_lis…
阅读更多...
套接字通信模型

套接字通信模型

本文内容主要参考《Android图形显示系统》 套接字也就是socket&#xff0c;一般用于网络中两个主机之间应用进程进行通信&#xff0c;在同一个主机也可以使用套接字完成进程之间的通信。 在图形显示系统中&#xff0c;用到套接字进行通信的地方主要有VSync信号的分发以及输入事…
阅读更多...
Linux：动态库加载、编址

Linux：动态库加载、编址

目录 一、库的概念 二、动静态库的加载 2.1绝对编址与相对编址 2.1一般程序的加载 三、动态库的加载 一、库的概念 库默认就是一个磁盘级文件&#xff0c;所以在执行代码时&#xff0c;库和可执行程序都会被加载到内存中&#xff0c;从原理上&#xff0c;库函数的调用依旧…
阅读更多...
软件测试：遇到bug怎么分析，这篇文章值得一看

软件测试：遇到bug怎么分析，这篇文章值得一看

为什么定位问题如此重要&#xff1f; 可以明确一个问题是不是真的“bug” 很多时候&#xff0c;我们找到了问题的原因&#xff0c;结果发现这根本不是bug。原因明确&#xff0c;误报就会降低多个系统交互&#xff0c;可以明确指出是哪个系统的缺陷&#xff0c;防止“踢皮球”&…
阅读更多...
C--函数指针与回调函数

C--函数指针与回调函数

文章目录 定义函数指针qsort中的回调函数自实现排序的回调函数 定义 回调函数&#xff0c;当一个函数执行时&#xff0c;中途调用其他定义好的函数来帮助实现功能&#xff0c;再继续执行这个函数 函数指针 类型为函数的指针&#xff0c;如下 void func() { } int main() {…
阅读更多...
如何让视频流媒体平台免受网络攻击

如何让视频流媒体平台免受网络攻击

在各国&#xff0c;流媒体服务已越来越受到大众的欢迎。有统计表明&#xff0c;目前视频流已占网络整体流量的80%以上。不过如您所见&#xff0c;近年来&#xff0c;数字威胁的不断增加&#xff0c;也让网络攻击逐年递增。单个视频用户受到的危险&#xff0c;往往会危及到整个服…
阅读更多...
【unity】【C#】游戏音乐播放和发布

【unity】【C#】游戏音乐播放和发布

今天我们来认识一下有关 unity 音乐的一些知识 我们先创建 AudioClips 文件夹&#xff0c;这个文件夹通常就是 unity 中存放音乐的文件夹&#xff0c;然后拖进音乐文件进去 这里为大家提供了两个音乐&#xff0c;有需要可以自取 百度网盘&#xff1a;https://pan.baidu.com/s…
阅读更多...
模型训练----apex库报错IndexError: tuple index out of range

模型训练----apex库报错IndexError: tuple index out of range

问题描述 在训练模型的过程中遇到了apex库的报错IndexError: tuple index out of range导致无法训练。在github查询后找到了解决方法 问题解决 需要修改/apex-master/apex/amp/utils.py这个文件的代码 从93行开始修改 if x in cache:cached_x cache[x]next_functions_ava…
阅读更多...
MySQL学习笔记（三）

MySQL学习笔记（三）

1、insert插入多条数据 语法&#xff1a;insert into t_user(字段名1,字段名2...) values(值1,值2...),(值1,值2...),(值1,值2...)...; 2、快速创建表 原理&#xff1a;将一个查询结果当做一张表创建&#xff0c;可以完成表的快速复制。表创建出来&#xff0c;同时表中的数据…
阅读更多...
计算机的发展趋势

计算机的发展趋势

本文 我们来说计算机的发展趋势 目前来讲 计算机是朝着 巨型化 微型化 网络化 智能化发展 巨型化 指功能巨型化 是指其高速运算、大存储容量和强功能的巨型计算机。其运算能力一般在每秒百亿次以上、内存容量在几百兆字节以上。 主要用于航空航天、军事、气象、人工智能、生…
阅读更多...
[Kubernetes[K8S]集群:master主节点初始化]：通过Calico和Coredns网络插件方式安装

[Kubernetes[K8S]集群:master主节点初始化]：通过Calico和Coredns网络插件方式安装

文章目录 操作流程&#xff1a;前置&#xff1a;Docker和K8S安装版本匹配查看0.1&#xff1a;安装指定docker版本 **[1 — 7] ** [ 配置K8S主从集群前置准备操作 ]一&#xff1a;主节点操作 查看主机域名->编辑域名->域名配置二&#xff1a;安装自动填充&#xff0c;虚拟…
阅读更多...
LeetCode 909 208

LeetCode 909 208

题目 909. 蛇梯棋 思路 完全不会&#xff01;呜呜呜&#xff0c;看了别人的题解。二维数组之字形遍历放在一维数组里面&#xff0c;然后借助队列对数组进行bfs。 代码 class Solution {int n;int[] nums;public int snakesAndLadders(int[][] board) {// 暴力遍历n board.le…
阅读更多...
深入理解图形处理器（GPU）：加速人工智能和大数据计算的引擎

深入理解图形处理器（GPU）：加速人工智能和大数据计算的引擎

文章目录 1. 什么是GPU&#xff1f;2. GPU的工作原理3. GPU的应用领域4. GPU与CPU的比较参考与推荐 前言&#xff1a; 图形处理器&#xff08;GPU&#xff09;不再仅仅是用于图形渲染的硬件设备。如今&#xff0c;GPU已经成为加速人工智能、大数据计算和科学研究的关键引擎。本…
阅读更多...
最新文章

Copyright @ 2022~2023