SSL 2250_面积_离散

发布于 2019-05-15  199 次阅读


题目描述

 数学老师画了两个长方形,如下图所示,长方形的边均平行于X轴、Y轴,长方形的四个顶点坐标均为整数且在0到1000之间,给出每个长方形的左下角坐标和右上角坐标,请你编一程序,求出两个长方形重叠部分的面积。


思路

先离散后求出整个图像的面积,然后用两个矩形的面积减去它就是答案

#include <stdio.h>
#include <algorithm>
using namespace std;
struct arr
{
    int x1,x2,y1,y2;
}a[1000];
int cam(int x,int y)
{
    return x<y;
}
int dx[1000],dy[1000],f[1000];
int main()
{
    int n,ll=0;
    ll++;
    n=2;
    int t=0;
    for (int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&a[i].x1,&a[i].y1,&a[i].x2,&a[i].y2);
        t++;
        dx[t]=a[i].x1; dy[t]=a[i].y1;
        t++;
        dx[t]=a[i].x2; dy[t]=a[i].y2;
    }
    sort(dx+1,dx+t+1,cam);
    sort(dy+1,dy+t+1,cam);
    int ans=0;
    for (int i=1;i<=t-1;i++)
    {
        int x1=dx[i],l=0,r=0;
        for (int j=1;j<=t-1;j++)
        {
            int y1=dy[j],x2=dx[i+1],y2=dy[j+1];
            if (x2==x1||y1==y2) continue;
            for (int k=1;k<=n;k++)
            {
                if (a[k].x1<=x1&&a[k].y1<=y1&&a[k].x2>x1&&a[k].y2>y1)
                {
                    ans+=(x2-x1)*(y2-y1);
                    break;
                 }
            }
        }
    }
    int x=(a[1].x2-a[1].x1)*(a[1].y2-a[1].y1),y=(a[2].x2-a[2].x1)*(a[2].y2-a[2].y1);
    ans=x+y-ans;
    printf("%d\n",ans);
}

「雪霁融雾月,冰消凝夜雨」