CF 1028C Rectangles 题解(思维)

题目链接

题目大意

给你(n(nle2e5))个长方形的左上角和右下角

要你找到一个点使得其位于(n-1)个长方形中

保证一定有解

题目思路

假设你要找到位于(n)个长方形重叠的面积，那么你可以直接维护左边界的最大值，右边界的最小值，上边界的最大值，下边界的最小值

然后就可以知道那个重叠的面积

这个题目利用这个思维，维护前缀的那些值，和后缀的那些值，即可，相当于删除一个矩形

代码

#include<bits/stdc++.h>
#define fi first
#define se second
#define debug cout<<"I AM HERE"<<endl;
using namespace std;
typedef long long ll;
const int maxn=2e5+5,inf=0x3f3f3f3f,mod=1e9+7;
const double eps=1e-6;
int n,m,q;
struct node{
    int x1,y1,x2,y2;
}a[maxn],pre[maxn],suf[maxn];
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].x1>>a[i].y1>>a[i].x2>>a[i].y2;
    }
    pre[0].x1=pre[0].y1=-inf;
    pre[0].x2=pre[0].y2=inf;
    for(int i=1;i<=n;i++){
        pre[i].x1=max(pre[i-1].x1,a[i].x1);
        pre[i].y1=max(pre[i-1].y1,a[i].y1);
        pre[i].x2=min(pre[i-1].x2,a[i].x2);
        pre[i].y2=min(pre[i-1].y2,a[i].y2);
    }
    suf[n+1].x1=suf[n+1].y1=-inf;
    suf[n+1].x2=suf[n+1].y2=inf;
    for(int i=n;i>=1;i--){
        suf[i].x1=max(suf[i+1].x1,a[i].x1);
        suf[i].y1=max(suf[i+1].y1,a[i].y1);
        suf[i].x2=min(suf[i+1].x2,a[i].x2);
        suf[i].y2=min(suf[i+1].y2,a[i].y2);

    }
    for(int i=1;i<=n;i++){
        node ans;
        ans.x1=max(pre[i-1].x1,suf[i+1].x1);
        ans.y1=max(pre[i-1].y1,suf[i+1].y1);
        ans.x2=min(pre[i-1].x2,suf[i+1].x2);
        ans.y2=min(pre[i-1].y2,suf[i+1].y2);
        if(ans.x2>=ans.x1&&ans.y2>=ans.y1){ // 表明有点在n-1个图中
            cout<<ans.x1<<" "<<ans.y1;
            break;
        }
    }
    return 0;
}