基础算法题——矩形面积相交

我不是女神ヾ 2023-07-10 08:13 92阅读 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