基础算法题——矩形面积相交 我不是女神ヾ 2023-07-10 08:13 60阅读 0赞 # 基础算法题——矩形面积相交 # 本人为一名普通二本学校自动化专业的大二学生,对编程有着少许兴趣。致力将算法写得更加通俗易懂。 ## 做题心得 ## 该题主要考查了判断、线段交,只要能够将矩形之间的关系弄清楚题目就会变得很简单。 ## 矩形面积相交题目 ## ![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70] ## 题目分析 ## 题目“对于每个矩形,我们给出它的一对相对顶点的坐标”,这也告诉了我们它的特殊情况会有很多,如果直接将数据记录下来然后就开始计算面积,无疑难度会很大,那我们有什么方法能够将数据“变形”到我们希望的样子呢? ###### 步骤一:变形(化简题目) ###### ①:通过观察可以得到每一行代表矩形的相对定点坐标(x1 y1 x2 y2),x与y可以组成四个不同的组合(我们假设每个值都不同),刚好对应矩形的四个顶点(这表示我们可以将x1、x2与y1、y2随意组合,组合数都是矩形的顶点)。 ②:我们可以将x1、y1作为矩形左下角的顶点、将x2、y2作为矩形右下角的顶点(将x1与x2比较,取较小的值作为x1,较大的值则作为x2。取y1同理)。 ③:两个矩形成功变形后,我们怎么知道哪个矩形在前面?哪个矩形在后面呢?可以将最左边的矩形作为a矩形(x1最小的矩形为a矩形)。 (为了方便描述分析,我将“变形”后的两个矩阵分别称为a矩形、b矩形) 变形后关系: a矩形:x1a<x2a y1a<y2a b矩形:x1b<x2b y1b<y2b ###### 步骤二:判断特殊情况(查漏) ###### ①:面积无相交 a矩形的x2a小于b矩阵的x1b a矩形的y2a小于b矩阵的y1b a矩形的y1a大于b矩阵的y2b ②:矩形无面积 矩形中出现x1=x2或y1=y2。 ###### 步骤三:计算相交面积(求解) ###### 我们可以知道要求两个矩形的相交面积,就要求△x、△y。 ①:通过观察当我们求△x时,我们要取两个矩形中最小的x2,然后减去两个矩形中最大的x1(这里可以简化计算,因为前面我们已经将有最小的x1a作为a矩形,这里我们可以比较两个矩形的x2,取最小作为x2小,然后减去b矩阵的x1b)。 **△x=x2小\-x1大** ②:同理求△y时,我们可以取两个矩形中最小的y2,然后减去两个矩形中最大的y1。 **△y=y2小\-y1大** ##### **S=△x\*△y** ##### 最后附上代码: #include<bits/stdc++.h> using namespace std; #define ll long long void change(double*a, double*b) { double temp; // cout<<"a:"<<*a<<endl; temp=*a; *a=*b; *b=temp; // cout<<"a:"<<*a<<endl; } int main() { double S, x, y; double jx[3][5]; for(int i=1; i<3; i++) for(int j=1; j<5; j++) cin>>jx[i][j]; // cout<<jx[1][1]<<endl; //第一个矩形 if(jx[1][1]>jx[1][3]) change(&jx[1][1], &jx[1][3]); if(jx[1][2]>jx[1][4]) change(&jx[1][2], &jx[1][4]); //第二个矩形 if(jx[2][1]>jx[2][3]) change(&jx[2][1], &jx[2][3]); if(jx[2][2]>jx[2][4]) change(&jx[2][2], &jx[2][4]); // cout<<jx[1][1]<<endl; // 判断无面积相交与无面积的情况 if(jx[1][3]<jx[2][1]|| //无相交面积 (jx[1][4]<jx[2][2]&&jx[1][2]<jx[2][4])|| (jx[2][4]<jx[1][2]&&jx[2][2]<jx[1][4])|| jx[1][4]<jx[2][2]||jx[1][1]==jx[1][3]|| //无面积 jx[2][1]==jx[2][3]||jx[1][2]==jx[1][4]||jx[2][2]==jx[2][4]) { printf("0.00"); return 0; } else { if(jx[1][3]>jx[2][3])//找x2小 x=jx[2][3]; else x=jx[1][3]; if(jx[1][1]>jx[2][1])//找x1大 x-=jx[1][1]; else x-=jx[2][1]; if(jx[1][4]>jx[2][4])//找y2小 y=jx[2][4]; else y=jx[1][4]; if(jx[1][2]>jx[2][2])//找y1大 y-=jx[1][2]; else y-=jx[2][2]; // cout<<x<<" "<<y<<endl; S=x*y; if(S>0) printf("%.2lf", S); else printf("0.00"); } return 0; } ## 总结 ## 这道算法题出自蓝桥杯基础练习,主要考查要点:判断、线段交。 如果对本题有其他看法的话,欢迎老铁给小郑留言。 ### 如果觉得该文章对你有用的话,可以给我一个大大的赞喔!! ### #### 老铁的关注是鼓励我写博客的最大动力~ #### ![被代码吃了][20200223150137342.png] [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200301030437830.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4=,size_16,color_FFFFFF,t_70 [20200223150137342.png]: https://img-blog.csdnimg.cn/20200223150137342.png
还没有评论,来说两句吧...