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

2024-04-12 05:04
文章标签 计算 笔记 蓝桥 纯小白 几何 day14 杯备赛

本文主要是介绍纯小白蓝桥杯备赛笔记--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，cbdouble 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;
}

二维计算几何基础

参考文献

这篇关于纯小白蓝桥杯备赛笔记--DAY14（计算几何）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/896173。

相关文章

uva 10387 Billiard（简单几何）

uva 10387 Billiard（简单几何）

题意是一个球从矩形的中点出发，告诉你小球与矩形两条边的碰撞次数与小球回到原点的时间，求小球出发时的角度和小球的速度。 简单的几何问题，小球每与竖边碰撞一次，向右扩展一个相同的矩形；每与横边碰撞一次，向上扩展一个相同的矩形。 可以发现，扩展矩形的路径和在当前矩形中的每一段路径相同，当小球回到出发点时，一条直线的路径刚好经过最后一个扩展矩形的中心点。 最后扩展的路径和横边竖边恰好组成一个直
阅读更多...
poj 1113 凸包+简单几何计算

poj 1113 凸包+简单几何计算

题意： 给N个平面上的点，现在要在离点外L米处建城墙，使得城墙把所有点都包含进去且城墙的长度最短。 解析： 韬哥出的某次训练赛上A出的第一道计算几何，算是大水题吧。 用convexhull算法把凸包求出来，然后加加减减就A了。 计算见下图： 好久没玩画图了啊好开心。 代码： #include <iostream>#include <cstdio>#inclu
阅读更多...
uva 1342 欧拉定理（计算几何模板）

uva 1342 欧拉定理（计算几何模板）

题意： 给几个点，把这几个点用直线连起来，求这些直线把平面分成了几个。 解析： 欧拉定理： 顶点数 + 面数 - 边数= 2。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc
阅读更多...
uva 11178 计算集合模板题

uva 11178 计算集合模板题

题意： 求三角形行三个角三等分点射线交出的内三角形坐标。 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <stack>#include <vector>#include <
阅读更多...
【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

【学习笔记】 陈强-机器学习-Python-Ch15 人工神经网络（1）sklearn

系列文章目录 监督学习：参数方法 【学习笔记】 陈强-机器学习-Python-Ch4 线性回归 【学习笔记】 陈强-机器学习-Python-Ch5 逻辑回归 【课后题练习】 陈强-机器学习-Python-Ch5 逻辑回归（SAheart.csv） 【学习笔记】 陈强-机器学习-Python-Ch6 多项逻辑回归 【学习笔记 及 课后题练习】 陈强-机器学习-Python-Ch7 判别分析 【学
阅读更多...
系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

系统架构师考试学习笔记第三篇——架构设计高级知识（20）通信系统架构设计理论与实践

本章知识考点：         第20课时主要学习通信系统架构设计的理论和工作中的实践。根据新版考试大纲,本课时知识点会涉及案例分析题(25分),而在历年考试中,案例题对该部分内容的考查并不多,虽在综合知识选择题目中经常考查,但分值也不高。本课时内容侧重于对知识点的记忆和理解,按照以往的出题规律,通信系统架构设计基础知识点多来源于教材内的基础网络设备、网络架构和教材外最新时事热点技术。本课时知识
阅读更多...
XTU 1237 计算几何

XTU 1237 计算几何

题面： Magic Triangle Problem Description: Huangriq is a respectful acmer in ACM team of XTU because he brought the best place in regional contest in history of XTU. Huangriq works in a big compa
阅读更多...
poj 3304 几何

poj 3304 几何

题目大意：给出n条线段两个端点的坐标，问所有线段投影到一条直线上，如果这些所有投影至少相交于一点就输出Yes！，否则输出No！。 解题思路：如果存在这样的直线，过投影相交点（或投影相交区域中的点）作直线的垂线，该垂线（也是直线）必定与每条线段相交，问题转化为问是否存在一条直线和所有线段相交。 若存在一条直线与所有线段相交，此时该直线必定经过这些线段的某两个端点，所以枚举任意两个端点即可。
阅读更多...
POJ 2318 几何 POJ 2398

POJ 2318 几何 POJ 2398

给出0 , 1 , 2 ... n 个盒子， 和m个点， 统计每个盒子里面的点的个数。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y
阅读更多...
poj 2653 几何

poj 2653 几何

按顺序给一系列的线段，问最终哪些线段处在顶端（俯视图是完整的）。 const double eps = 1e-10 ;double add(double x , double y){if(fabs(x+y) < eps*(fabs(x) + fabs(y))) return 0 ;return x + y ;}struct Point{double x , y ;Point(){}Po
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2