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[<<], *O = obuf;

#define OS  *O++ = ' ';

using namespace std;

using namespace __gnu_pbds;

const int MAXN = 1e6 + , INF = 1e9 + , mod = 1e9 + ;

const double eps = 1e-;

inline int read() {

    char c = getchar(); int x = , f = ;

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') x = x *  + c - '', c = getchar();

    return x * f;

}

int N;

void print(int x) {

    if(x > ) print(x / );

    *O++ = x %  + '';

}

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 = ; i <= N; i++) {

        P[i].x1 = read(); P[i].y1 = read();

        P[i].x2 = read(); P[i].y2 = read();

    }

    A[] = P[]; for(int i = ; i <= N; i++) A[i] = A[i - ] + P[i];

    B[N] = P[N]; for(int i = N - ; i >= ; i--) B[i] = B[i + ] + P[i];

    for(int i = ; i <= N; i++) {

        Point cur;

        if(i == ) cur = B[];

        else if(i == N) cur = A[N - ];

        else cur = A[i - ] + B[i + ];

        if(cur.x1 <= cur.x2 && cur.y1 <= cur.y2) {

            printf("%d %d", cur.x1, cur.y1);

            return ;

        }

    }

    return ;

}

/*

*/