首页 > > 程序设计 > C/C++ >

cf1028C. Rectangles(前缀和)

2018-09-01 05:37:48来源：博客园阅读 ()

题意

给出$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;
}
/*

*/