本文共 1521 字，大约阅读时间需要 5 分钟。
题目：
题意：有n个矩阵，求一个点（保证存在）至少在n-1个点内。
解题思路：因为矩阵与坐标轴平行，所以我们画图可以发现如果存在点满足条件，则这些点中一定有一个是矩阵的顶点。我们可以把所有顶点的横纵坐标分别存下来排序，左下角的最大两个横纵坐标与右上角的最小两个横纵坐标相互结合，一定有一个是答案。如果不明白可以看看1029C，算是这题的一维简化版。
附ac代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 using namespace std;10 typedef long long ll;11 const int maxn = 132674 + 10;12 int n;13 struct nod14 {15 int x;16 int y;17 18 }nua[maxn], nub[maxn];19 int l[maxn], r[maxn], u[maxn], d[maxn];20 void print(int lc, int dc)21 {22 int cnt = 0;23 for(int i = 1; i <= n; ++i)24 {25 if(lc >= nua[i].x && lc <= nub[i].x && dc >= nua[i].y && dc <= nub[i].y)26 {27 ++cnt;28 }29 }30 if(cnt >= n - 1)31 {32 printf("%d %d\n", lc, dc);33 exit(0);34 }35 }36 int main()37 {38 39 scanf("%d", &n);40 for(int i = 1; i <= n; ++i)41 {42 scanf("%d %d %d %d", &l[i], &d[i], &r[i], &u[i]);43 nua[i].x = l[i];44 nua[i].y = d[i];45 nub[i].x = r[i];46 nub[i].y = u[i];47 }48 sort(l + 1, l + 1 + n);49 sort(r + 1, r + 1 + n);50 sort(d + 1, d + 1 + n);51 sort(u + 1, u + 1 + n);52 for(int i = 1; i <= 2; ++i)53 {54 for(int j = n - 1; j <= n; ++j)55 {56 print(l[j], u[i]);57 print(r[i], d[j]);58 }59 for(int j = 1; j <= 2; ++j)60 {61 print(l[i], d[j]);62 }63 }64 for(int i = n - 1; i <= n; ++i)65 {66 for(int j = n - 1; j <= n; ++j)67 {68 print(r[i], u[i]);69 }70 }71 return 0;72 }
转载于:https://www.cnblogs.com/zmin/p/9591873.html
