两个矩阵面积并——————简单几何

灰太狼 2022-02-25 11:42 206阅读 0赞

今年校赛出了一道两个矩阵面积并的问题，当时脑子抽了，想要把所有情况都考虑出来，但是情况太多了，又看了一眼题，发现数据全是整数，范围才1000，于是开了一个1000\*1000的二维矩阵，将在矩阵之间的面积标记为1，其他的标记为0，再看看有多少个1，那么两个矩阵的面积就是1的个数

然而实际上正解是如此简介…

# [H. Mo的面积][H. Mo] #

单测试点时限: 1.0 秒

内存限制: 512 MB

Mo的老师给了他两个矩形，让他求两个矩形的面积并。Mo很忙没时间解决这种小case，请你帮他解决。

输入  
输入两行，每行四个整数 x,y,x1,y1 。(x,y) 是矩形左下角，(x1,y1) 是矩形的右上角. (0≤x,y,x1,y1≤1000)。

输出  
输出一个整数表示二个矩形的面积并。

样例  
input  
0 1 2 3  
1 0 3 2  
output  
7

我的代码：

#include<bits/stdc++.h>
    using namespace std;
    const int MAXN = 1e3+7;
    bool vis[MAXN][MAXN];
    
    
    int main()
    {
        
    	int a1,b1,c1,d1;
    	int a2,b2,c2,d2;
    	cin>>a1>>b1>>c1>>d1;
    	cin>>a2>>b2>>c2>>d2;
    	memset(vis,0,sizeof(vis));
    	for(int i=a1;i<c1;++i)
    		for(int j=b1;j<d1;++j)
    			vis[i][j] = 1;
    	for(int i=a2;i<c2;++i)
    		for(int j=b2;j<d2;++j)
    			vis[i][j] = 1;
    	int ans = 0;
    	for(int i=0;i<MAXN;++i)
    		for(int j=0;j<MAXN;++j)
    			if(vis[i][j])	ans++;	
    	cout<<ans<<endl;
    	return 0;
    }

其他写法（这个才是正宗写法），

#include<bits/stdc++.h>
    using namespace std;
    
    int a[10];
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            for(int i=1;i<=8;++i)   cin>>a[i];
            int l = max( min(a[1], a[3]), min(a[5], a[7]));
            int d = max( min(a[2], a[4]), min(a[6], a[8]));
            int r = min( max(a[1], a[3]), max(a[5], a[7]));
            int u = min( max(a[2], a[4]), max(a[6], a[8]));
            int sum = abs(a[1]-a[3])*abs(a[2]-a[4]) + abs(a[5]-a[7])*abs(a[6]-a[8]);
            int ans = 0;
            if(l>=r||d>=u)  ans = 0;
            else            ans = (r-l)*(u-d);
            cout<<sum-ans<<endl;
            return 0;
    }

--------------------

HDU上也有一道类似的问题

# [HDU 2056 Rectangles][] #

Rectangles  
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 33282 Accepted Submission(s): 10759

Problem Description  
Given two rectangles and the coordinates of two points on the diagonals of each rectangle,you have to calculate the area of the intersected part of two rectangles. its sides are parallel to OX and OY .

Input  
Input The first line of input is 8 positive numbers which indicate the coordinates of four points that must be on each diagonal.The 8 numbers are x1,y1,x2,y2,x3,y3,x4,y4.That means the two points on the first rectangle are(x1,y1),(x2,y2);the other two points on the second rectangle are (x3,y3),(x4,y4).

Output  
Output For each case output the area of their intersected part in a single line.accurate up to 2 decimal places.

Sample Input  
1.00 1.00 3.00 3.00 2.00 2.00 4.00 4.00  
5.00 5.00 13.00 13.00 4.00 4.00 12.50 12.50

Sample Output  
1.00  
56.25

给你两个矩阵，求它们相交的部分

#include<bits/stdc++.h>
    using namespace std;
    
    double a[10];
    
    int main()
    {
        
            // freopen("../in.txt","r",stdin);
            // freopen("../out.txt","w",stdout);
            while(cin>>a[1]>>a[2]>>a[3]>>a[4]>>a[5]>>a[6]>>a[7]>>a[8])
            {
        
                    // for(int i=1;i<=8;++i)   cin>>a[i];
                    double l = max( min(a[1], a[3]), min(a[5], a[7]));
                    double d = max( min(a[2], a[4]), min(a[6], a[8]));
                    double r = min( max(a[1], a[3]), max(a[5], a[7]));
                    double u = min( max(a[2], a[4]), max(a[6], a[8]));
                    double sum = abs(a[1]-a[3])*abs(a[2]-a[4]) + abs(a[5]-a[7])*abs(a[6]-a[8]);
                    double ans = 0;
                    if(l>=r||d>=u)  ans = 0;
                    else            ans = (r-l)*(u-d);
                    // cout<<ans<<endl;
                    printf("%.2f\n",ans);
            }
    
            return 0;
    }

[H. Mo]: https://hpuoj.com/contest/16/problem/H/
[HDU 2056 Rectangles]: http://acm.hdu.edu.cn/showproblem.php?pid=2056