cf1028C. Rectangles(前缀和)

题意

给出$n$个矩形，找出一个点，使得至少在$n$个矩阵内

sol

呵呵哒，昨天cf半夜场，一道全场切的题，我没做出来。。不想找什么理由，不会做就是不会做。。

一个很显然的性质，如果存在一个点 / 矩形在$n - 1$个矩形内的话

它们的交集不会是空集。

然后我们去枚举每个点，假设他不与$(n - 1)$个矩形相交，前缀和后缀和判一下就行

/*

*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<cmath>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define pair pair<int, int>
#define mp(x, y) make_pair(x, y)
#define fi first
#define se second
//#define int long long 
#define ll long long 
#define rg register 
#define sc(x) scanf("%d", &x);
#define pt(x) printf("%d ", x);
#define db(x) double x 
#define rep(x) for(int i = 1; i <= x; i++)
//#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1<<22, stdin), p1 == p2) ? eof : *p1++)
//char buf[(1 << 22)], *p1 = buf, *p2 = buf;
char obuf[1<<24], *o = obuf;
#define os  *o++ = ' ';
using namespace std;
using namespace __gnu_pbds;
const int maxn = 1e6 + 10, inf = 1e9 + 10, mod = 1e9 + 7;
const double eps = 1e-9;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n;
void print(int x) {
    if(x > 9) print(x / 10);
    *o++ = x % 10 + '0';
}
struct point {
    int x1, y1, x2, y2;
    point operator + (const point &rhs) const {
        return (point) {max(x1, rhs.x1), max(y1, rhs.y1), min(x2, rhs.x2), min(y2, rhs.y2)};
    }
}p[maxn], a[maxn], b[maxn];
main() {
    n = read(); 
    for(int i = 1; i <= n; i++) {
        p[i].x1 = read(); p[i].y1 = read();
        p[i].x2 = read(); p[i].y2 = read();
    }
    a[1] = p[1]; for(int i = 2; i <= n; i++) a[i] = a[i - 1] + p[i];
    b[n] = p[n]; for(int i = n - 1; i >= 1; i--) b[i] = b[i + 1] + p[i];
    for(int i = 1; i <= n; i++) {
        point cur;
        if(i == 1) cur = b[2];
        else if(i == n) cur = a[n - 1];
        else cur = a[i - 1] + b[i + 1];
        
        if(cur.x1 <= cur.x2 && cur.y1 <= cur.y2) {
            printf("%d %d", cur.x1, cur.y1); 
            return 0;
        }
    }
    return 0;
}
/*

*/