求解 (矩形重叠的问题)哪位大神帮忙分析下(答案在我的题解里面)
求解 (矩形重叠的问题)
哪位大神帮忙分析下哪位大神帮忙分析下
我的代码在测试运行的时候,跑到第4列时NG。
预期输出 11
实际输出 39
题目是
平面内有n个矩形, 第i个矩形的左下角坐标为(x1[i], y1[i]), 右上角坐标为(x2[i], y2[i])。
如果两个或者多个矩形有公共区域则认为它们是相互重叠的(不考虑边界和角落)。
请你计算出平面内重叠矩形数量最多的地方,有多少个矩形相互重叠。
输入描述:
输入包括五行。
第一行包括一个整数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 <= x2[i] <= 10^9),表示右上角的横坐标。
第五行包括n个整数y2[i](-10^9 <= y2[i] <= 10^9),表示右上角的纵坐标。
输出描述:
输出一个正整数, 表示最多的地方有多少个矩形相互重叠,如果矩形都不互相重叠,输出1。
我的代码是
include<stdio.h>
int main()
{
int n;
int sz[50][4]={0};
scanf("%d",&n);
for(int j=0;j<4;j++){
for(int i=0;i<n;i++){
scanf("%d",&sz[i][j]);
}
}//录入信息
for(int i=0;i<n;i++){
int tmp;
if(sz[i][3]<sz[i][1]){tmp=sz[i][3];sz[i][3]=sz[i][1];sz[i][1]=tmp;}
if(sz[i][2]<sz[i][0]){tmp=sz[i][2];sz[i][2]=sz[i][0];sz[i][0]=tmp;}
}//保证右上角大于左下角
int tmp=1;
for(int i=0;i<n;i++){
int count=1;
for(int j=0;j<n;j++){
if(i==j) continue;
if((sz[i][3]>sz[j][1])&&(sz[i][2]>sz[j][0])&&(sz[j][3]>sz[i][1])&&(sz[j][2]>sz[i][0])){
count++;
}//如果j矩形的右上角大于i矩形的左下角,且i矩形的右上角大于j矩形的左下角,则矩形重合
}
if(count>tmp) {tmp=count;}
}
printf("%d\n",tmp);
return 0;
}