平面有n个矩形，第一个矩形左下标为（x1[1],y1[1]）,右上标为（x2[1],y2[1]）.
如果有2个或多个矩形有公共区域则认为他们相互重叠
计算平面内重叠矩形数量最多的地方有几个矩形相互重叠
输入
第一行n（2<=n<=50）,表示矩形的个数
第二行n个整数x1[i] （-10^9<=x1[i]<=10^9）,表示左下角的横坐标
第三行 n个整数y1[i] （-10^9<=y1[i]<=10^9）,表示左下角的纵坐标
第四行n个整数x2[i] （-10^9<=x1[i]<=10^9）,表示右上角的横坐标
第五行 n个整数y2[i] （-10^9<=y1[i]<=10^9）,表示右上角的纵坐标
输出
输出一个正整数， 表示最多的地方有几个矩形相互重叠，如果都不重叠输出1；
测试数据：
2
0 90
0 90
100 200
100 200
#include <iostream> #include <cstdio> #include <cstring> #include <cmath> #include <cstdlib> #include <algorithm> using namespace std; struct node { double x1; //矩形左下角横坐标 double y1; //矩形左下角纵坐标 double x2; //矩形右上角横坐标 double y2; //矩形右上角纵坐标 int t; }; node c; int fan(node a,node b) //判断a,b两个矩形是否相交，矩形c是相交矩阵 { double xc1,xc2,yc1,yc2; xc1=max(a.x1,b.x1); xc2=min(a.x2,b.x2); yc1=max(a.y1,b.y1); yc2=min(a.y2,b.y2); if(xc1<xc2&&yc1<yc2) { c.x1=xc1; c.y1=yc1; c.x2=xc2; c.y2=yc2; return 1; } else return 0; } int main() { int n; int x1[55]; int y1[55]; int x2[55]; int y2[55]; node nodes[55]; while(cin>>n) { for(int i=1; i<=n; i++) { cin>>nodes[i].x1; } for(int i=1; i<=n; i++) { cin>>nodes[i].y1; } for(int i=1; i<=n; i++) { cin>>nodes[i].x2; } for(int i=1; i<=n; i++) { cin>>nodes[i].y2; } //最长递增子序列的模版 node dp[55]; int pre[55]; //memset(dp,0,sizeof(dp)); memset(pre,0,sizeof(pre)); int maxs=1; int k=0; for(int i=1; i<=n; i++) { pre[i]=i; //开始的地方 dp[i].x1=nodes[i].x1; dp[i].y1=nodes[i].y1; dp[i].x2=nodes[i].x2; dp[i].y2=nodes[i].y2; dp[i].t=1; //递增的长度 for(int j=1; j<i; j++) { if(fan(dp[i],nodes[j])&&dp[i].t<dp[j].t+1) { k=1; dp[i].x1=c.x1; dp[i].y1=c.y1; dp[i].x2=c.x2; dp[i].y2=c.y2; dp[i].t=dp[j].t+1; pre[i]=j; } } if(dp[i].t>maxs) { maxs=dp[i].t; } } if(k==0) cout<<"1"; else cout<<maxs<<endl; } return 0; }