题意
给出$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; } /* */
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/608314.html