首页 > 试题广场 >

矩形重叠

[编程题]矩形重叠
  • 热度指数：22827 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解

平面内有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。
示例1

输入

2
0 90
0 90
100 200
100 200

输出

2
算法知识视频讲解
添加回答
tuweilong头像 tuweilong 
/*
无论何种情况，重叠区域也是四条边组成。
而且是取自与n的矩形中的四条。
所以遍历边的交点即可。
*/
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x1 = new int[n];
        int[] y1 = new int[n];
        int[] x2 = new int[n];
        int[] y2 = new int[n];
        int xmin = Integer.MAX_VALUE;
        int xmax = Integer.MIN_VALUE;
        int ymin = Integer.MAX_VALUE;
        int ymax = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) 
            x1[i] = in.nextInt();
        for (int i = 0; i < n; i++) 
            y1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            x2[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            y2[i] = in.nextInt();
        int ans = 0;
        int cnt = 0;
        for (int x : x1)
            for (int y : y1) {
                for (int i = 0; i < n; i++) {
                    if (x >= x1[i] && x < x2[i] && y >= y1[i] && y < y2[i])
                        cnt++;
                }
                if (cnt > ans)
                    ans = cnt;
                cnt = 0;
            }
        System.out.println(ans);
    }
}

发表于 2019-06-26 13:15:59 回复(26)
Yummy蛋卷头像 Yummy蛋卷

注意判断重叠矩形数量最多的地方：遍历所有可能包含的点,看一下有多少矩形包含它
注：重叠数量最多的地方肯定是一块矩形区域

误区：A和B交，B和C交，但是A不和C交 --- B同时和A,C交, 但是重叠区域只为1

代码如下：

import sys
lines = sys.stdin.readlines()
n = int(lines[0])
x1 = list(map(int,lines[1].split()))
y1 = list(map(int,lines[2].split()))
x2 = list(map(int,lines[3].split()))
y2 = list(map(int,lines[4].split()))
# 遍历所有点的组合（包含了矩形所有角以及交点），看一下有多少矩形包含它
res = 1
for x in x1+x2:
    for y in y1+y2:
        cnt = 0
        for i in range(n):
            if x > x1[i] and y > y1[i] and x <= x2[i] and y <= y2[i]:
                cnt += 1
        res = max(res,cnt)
print(res)
编辑于 2018-03-29 10:28:39 回复(23)
C/C++
笋也可以头像 笋也可以

O(n^2logn)算法。
思路是首先对所有矩形排序，按照底边坐标值升序。

考虑到若将平面按照所有矩形的的底边坐标值横向划分，每个划分中的最大重合情况总是出现在该划分底部，且等价一维的区间重合问题。如图所示:
图片说明
因此，我们每次迭代将下一个或多个底边坐标值最低的矩阵加入队列，并将整个在当前最低坐标值之下的矩形从队列中移除，然后用区间重合的算法计算队列中矩形在目前划分的重合数量。

以下是代码： 

#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <algorithm>
#include <map>
#include <limits.h>
using namespace std;
// square overlap
class Square{
public:
    int left, right, up, down;
    bool operator <(const Square &x){
        return down < x.down;
    }
};

bool leftto(Square a, Square b){
    return a.left < b.left;
}

void eraselower(vector<Square> &a, int ybound){
    int deln = 0, i = 0, n = a.size();
    while(i + deln < n){
        if(a[i].up<=ybound)
            swap(a[i], a[n-(++deln)]);
        else
            ++i;
    }
    a.erase(a.end()-deln, a.end());
}

int main(){
    int n;
    cin>>n;
    vector<Square> sqs(n), row;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].left;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].down;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].right;
    for(int i=0; i<n; ++i)
        cin>>sqs[i].up;
    sort(sqs.begin(), sqs.end());
    int sn = 0, curdown = 0, res = 0;
    while(sn<n){
        curdown = sqs[sn].down;
        while(sn<n && sqs[sn].down == curdown)
            row.push_back(sqs[sn++]);
        eraselower(row, curdown);
        sort(row.begin(), row.end(), leftto);
        vector<int> rights;
        for(Square x:row){
            rights.erase(rights.begin(), upper_bound(rights.begin(), rights.end(), x.left));
            rights.insert(upper_bound(rights.begin(), rights.end(), x.right), x.right);
            if(res < rights.size()) res = rights.size();
        }
    }
    cout<<res<<endl;
}
编辑于 2018-04-12 15:30:39 回复(12)
Hewitt头像 Hewitt
考虑把每个矩形的左下角和右上角坐标离散化，最终N个矩形可以看成存在于一个2N*2N的方格中，方格中每个点的权值为该点出现矩形的个数，扫一遍维护最大值即为答案。 
#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int x1[N],y11[N],x2[N],y2[N],X[2*N],Y[2*N];
int mp[2*N][2*N],p,q,lx,ly,rx,ry;
void color(){   ///将矩形出现在方格中的点全部+1
    for(int i=lx+1;i<=rx;i++)for(int j=ly+1;j<=ry;j++){ ///由于边界不算，所以从lx+1开始
        mp[i][j]++;
    }
}
int main(){
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)scanf("%d",&x1[i]),X[i]=x1[i];
    for(int i=0;i<n;i++)scanf("%d",&y11[i]),Y[i]=y11[i];
    for(int i=0;i<n;i++)scanf("%d",&x2[i]),X[i+n]=x2[i];
    for(int i=0;i<n;i++)scanf("%d",&y2[i]),Y[i+n]=y2[i];
    sort(X,X+2*n);         ///离散化过程
    sort(Y,Y+2*n);
    p = unique(X,X+2*n)-X; 
    q = unique(Y,Y+2*n)-Y;
    for(int i=0;i<n;i++){
        lx = lower_bound(X,X+p,x1[i])-X;  ///查询离散化之后出现在方格的左下角和右上角坐标
        ly = lower_bound(Y,Y+q,y11[i])-Y;
        rx = lower_bound(X,X+p,x2[i])-X;
        ry = lower_bound(Y,Y+q,y2[i])-Y;
        color();
    }
    int ans = 1;
    for(int i=0;i<p;i++)for(int j=0;j<q;j++)ans = max(ans,mp[i][j]);
    printf("%d\n",ans);
    return 0;
}

发表于 2019-06-28 09:36:38 回复(3)
C/C++
数学&amp;curren;lover头像 数学&amp;curren;lover
看n的范围就能知道这道题可以支持几乎所有的多项式复杂度的算法了，我的算法是O(n^3)的复杂度。其实可以做到O(n^2logn)，但是要用到线段树，对于n<=50的规模来说可能会因为常数大程序反而跑得更慢。
首先因为坐标的范围是1e9，因此第一步肯定是对坐标进行离散化，我们存下所有的x坐标和y坐标，然后分别进行排序。然后我们得到了两个数组，一个是x坐标的数组，一个是y坐标的数组，分别都有2n个整数，这2个数组把平面分成了(2n-1)*(2n-1)个格子。所有的初始矩形都由这些格子组成
我们可以取这些格子的对角线中点(共(2n-1)(2n-1)个)代表这些格子，然后考虑这些这些点分别包含在多少个矩形中。然后求出被覆盖最多次的格子就是答案了。
发表于 2018-03-28 01:50:20 回复(7)
InsZVA201905212147812头像 InsZVA201905212147812
可能是全网最快解法 O(NlogN)
先离散化纵坐标，然后用扫描线算法，用线段树维护区间最大值。
排序纵坐标的复杂度O(NlogN)，扫描线扫描复杂度O(N)*线段树操作复杂度O(logN)。
代码如下： 
#include <iostream>
#include <cstdio>
#include <vector>
#include <string>
#include <queue>
#include <cstring>
#include <utility>
#include <climits>
#include <unordered_map>
#include <algorithm>
#include <stack>
#include <cmath>
#include <map>
#include <numeric>
#define LL long long
#define M 1000000007
#define M2 998244353
#define MAXN 105
#define eps 1e-7

using namespace std;

struct Node {
    int s, e, val, tag;
};
Node seg[MAXN*4];

void build(int idx, int s, int e) {
    seg[idx].s = s, seg[idx].e = e;
    int m = (s+e)/2;
    if (s == e) return;
    build(idx*2, s, m), build(idx*2+1, m+1, e);
}

void update(int idx, int start, int end, int off) {
    //cout << "update:" << start << "," << end << ":" << off << endl;
    if (start == seg[idx].s && end == seg[idx].e) {
        seg[idx].tag += off;
        seg[idx].val += off;
        return;
    }
    
    int m = (seg[idx].s+seg[idx].e)/2;
    if (seg[idx].tag) {
        update(idx*2, seg[idx].s, m, seg[idx].tag);
        update(idx*2+1, m+1, seg[idx].e, seg[idx].tag);
        seg[idx].tag = 0;
    }
    
    if (end <= m) update(idx*2, start, end, off);
    else if (start > m) update(idx*2+1, start, end, off);
    else {
        update(idx*2, start, m, off);
        update(idx*2+1, m+1, end, off);
    }
    seg[idx].val = max(seg[idx*2].val, seg[idx*2+1].val);
}

int query(int idx, int start, int end) {
    if (seg[idx].s == start && seg[idx].e == end) {
        return seg[idx].val;
    }

    int m = (seg[idx].s+seg[idx].e)/2;
    if (seg[idx].tag) {
        update(idx*2, seg[idx].s, m, seg[idx].tag);
        update(idx*2+1, m+1, seg[idx].e, seg[idx].tag);
        seg[idx].tag = 0;
    }

    if (end <= m) return query(idx*2, start, end);
    else if (start > m) return query(idx*2+1, start, end);
    else return max(query(idx*2, start, m), query(idx*2+1, m+1, end));
}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin >> n;
    vector<int> x1(n), y1(n), x2(n), y2(n);
    vector<int> ys;
    for (int i = 0; i < n; i++) cin >> x1[i];
    for (int i = 0; i < n; i++) cin >> y1[i];
    for (int i = 0; i < n; i++) cin >> x2[i];
    for (int i = 0; i < n; i++) cin >> y2[i];
    for (int i = 0; i < n; i++) ys.push_back(y1[i]), ys.push_back(y2[i]);
    sort(ys.begin(), ys.end());
    ys.resize(unique(ys.begin(), ys.end()) - ys.begin());
    unordered_map<int, int> y2i;
    for (int i = 0; i < ys.size(); i++) y2i[ys[i]] = i;
    vector<vector<int>> v;
    for (int i = 0; i < n; i++) {
        v.push_back({x1[i], 1, y2i[y1[i]], y2i[y2[i]]});
        v.push_back({x2[i], -1, y2i[y1[i]], y2i[y2[i]]});
    }
    sort(v.begin(), v.end(), [](const vector<int>& v1, const vector<int>& v2) {
        return v1[0] < v2[0] || v1[0] == v2[0] && v1[1] < v2[1];
    });
    int res = 0;
    build(1, 0, ys.size());
    int lastx = INT_MIN;
    for (auto& vv: v) {
        if (lastx == INT_MIN && vv[1] < 0) continue;
        //cout << vv[0] <<  "," << vv[1] << "," << vv[2] << "," << vv[3] << endl;
        if (vv[0] != lastx) {
            //cout << query(1, 0, ys.size()) << endl;
            res = max(res, query(1, 0, ys.size()));
            lastx = vv[0];
        }
        update(1, vv[2], vv[3]-1, vv[1]);
    }
    //cout << query(1, 0, ys.size()) << endl;
    res = max(res, query(1, 0, ys.size()));
    cout << res << endl;
    return 0;
}


发表于 2019-10-24 22:28:32 回复(0)
布拉佛斯的冰原狼头像 布拉佛斯的冰原狼 

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Scanner;

class edge implements Comparable{
    Integer left;
    Integer right;
    Integer height;
    Integer value;
    edge(int left,int right,int height,int value){
        this.left=left;
        this.right=right;
        this.height=height;
        this.value=value;
    }
    @Override
    public int compareTo(Object o) {
        return Integer.compare(height,((edge)o).height);
    }
}
public class Main {
    public static void main(String[] args){
        ArrayList<Integer> xAxial=new ArrayList<Integer>();
        ArrayList<edge> allEdges=new ArrayList<>();
        Scanner in=new Scanner(System.in);
        int n=in.nextInt();
        int[] x1=new int[n];
        int[] x2=new int[n];
        int[] y1=new int[n];
        int[] y2=new int[n];
        for(int i=0;i<n;++i){
            x1[i]=in.nextInt();
            xAxial.add(x1[i]);
        }
        for(int i=0;i<n;++i){
            y1[i]=in.nextInt();
        }
        for(int i=0;i<n;++i){
            x2[i]=in.nextInt();
            xAxial.add(x2[i]);
        }
        for(int i=0;i<n;++i){
            y2[i]=in.nextInt();
        }
        for(int i=0;i<n;++i){
            allEdges.add(new edge(x1[i],x2[i],y1[i],1));
            allEdges.add(new edge(x1[i],x2[i],y2[i],-1));
        }
        Collections.sort(xAxial);
        Collections.sort(allEdges);
        ArrayList<Integer> count=new ArrayList<Integer>();
        for(int i=0;i!=xAxial.size()-1;++i)
            count.add(0);
        int result=1;
        for(edge tmp : allEdges){
            Integer index=xAxial.indexOf(tmp.left);
            while(xAxial.get(index)<tmp.right){
                count.set(index,count.get(index)+tmp.value);
                if(count.get(index)>result){
                    result=count.get(index);
                }
                ++index;
            }
        }
        System.out.println(result);
    }
}

编辑于 2018-03-28 16:21:31 回复(2)
KeepGoingOn头像 KeepGoingOn 
#include <bits/stdc++.h>
using namespace std;

int main()
{
    //读取输入
    int n;
    cin>>n;
    int x1[n],y1[n],x2[n],y2[n];//左下x,左下y，右上x,右下y
    for(int i = 0;i<n;i++)
        cin>>x1[i];
    for(int i = 0;i<n;i++)
        cin>>y1[i];
    for(int i = 0;i<n;i++)
        cin>>x2[i];
    for(int i = 0;i<n;i++)
        cin>>y2[i];
    int result = 0;
    //二维转一维，遍历左下角点的x和y，看这些点在多少个矩形内
    for(int x: y1)
        for(int y: y1)
        {
            int cnt =0;
            for(int j=0;j<n;j++)
            {
                //注意判断条件，一开一闭，否则两个完全重合的矩形会多计算一次
                if(x>=x1[j]&&x<x2[j]&&y>=y1[j]&&y<y2[j])
                    cnt++;
            }
            result = max(cnt,result);
        }
    cout<<result<<endl;
    return 0;
}
            

发表于 2019-09-07 10:04:25 回复(4)
-birchy头像 -birchy 
import sys
n=int(sys.stdin.readline().strip())
x1=list(map(int,sys.stdin.readline().strip().split()))
y1=list(map(int,sys.stdin.readline().strip().split()))
x2=list(map(int,sys.stdin.readline().strip().split()))
y2=list(map(int,sys.stdin.readline().strip().split()))
res = 1
for x in x1+x2:
    for y in y1+y2:
        cnt = 0
        for i in range(n):
            if x > x1[i] and y > y1[i] and x <= x2[i] and y <= y2[i]:
                cnt += 1
        res = max(res,cnt)
print(res)

发表于 2019-08-25 05:25:57 回复(0)
Python
ElonB头像 ElonB 
"""
重叠的区域角横坐标x必然是【x1，x2】中某个值
重叠的区域角横坐标y必然是【y1，y2】中某个值
遍历所有坐标点（x,y），由于重叠不考虑边界和角落
    在 x_range, y_range = x ± δ, y ± δ （δ< 1)
    x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i] 范围内计算重叠个数
    或者 x1[i] < x <= x2[i] and y1[i] < y <= y2[i] ，等号的位置等同于上式的±号。
取所有坐标点最大的重叠个数即为所求
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    n = int(input().strip())
    x1 = list(map(int, input().strip().split()))
    y1 = list(map(int, input().strip().split()))
    x2 = list(map(int, input().strip().split()))
    y2 = list(map(int, input().strip().split()))
    ans = 1
    for x in x1 + x2:
        for y in y1 + y2:
            x_range, y_range = x - 0.1, y - 0.1
            cnt = 0
            for i in range(n):
                if x1[i] < x_range < x2[i] and y1[i] < y_range < y2[i]:
                # if x1[i] < x <= x2[i] and y1[i] < y <= y2[i]:
                    cnt += 1
            ans = max(ans, cnt)
    print(ans)

发表于 2019-07-02 19:55:20 回复(3)
FlushHip头像 FlushHip

CSDN: 网易2019实习生招聘编程题集合 - 题解
GitHub:
网易2019实习生招聘编程题集合
牛客网：

https://www.nowcoder.com/discuss/70894

发表于 2018-03-28 18:13:48 回复(0)
李大爷223头像 李大爷223
//通过了
#include <iostream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <string>
using namespace std;
class juxing
{
public:
int lb_x;
int lb_y;
int rt_x;
int rt_y;
juxing(int a, int b, int c, int d): lb_x(a), lb_y(b), rt_x(c), rt_y(d){}
};
int main()
{
int n;
scanf("%d", &n);

vector<int> lbX(n);
for (int i = 0; i < n; i++)
scanf("%d", &lbX[i]);
vector<int> lbY(n);
for (int i = 0; i < n; i++)
scanf("%d", &lbY[i]);
vector<int> rtX(n);
for (int i = 0; i < n; i++)
scanf("%d", &rtX[i]);
vector<int> rtY(n);
for (int i = 0; i < n; i++)
scanf("%d", &rtY[i]);

vector<juxing> AllJuXing;
for (int i = 0; i < n; i++)
AllJuXing.push_back(juxing(lbX[i], lbY[i], rtX[i], rtY[i]));
vector<int> XX;
for (int i = 0; i < n; i++)
{
XX.push_back(lbX[i]);
XX.push_back(rtX[i]);
}
vector<int> YY;
for (int i = 0; i < n; i++)
{
YY.push_back(lbY[i]);
YY.push_back(rtY[i]);
}

int count = 0, ret = 0;
for (int i = 0; i < XX.size(); i++)
{
for (int j = 0; j < YY.size(); j++)
{
for (int k = 0; k < AllJuXing.size(); k++)
{
if (XX[i] >= AllJuXing[k].lb_x && XX[i] < AllJuXing[k].rt_x && YY[j] >= AllJuXing[k].lb_y && YY[j] < AllJuXing[k].rt_y)
count ++;
}
ret = max(ret, count);
count = 0;
}
}
cout<<ret;
return 0;
}

编辑于 2018-03-28 17:30:32 回复(0)
粗心的肱二头肌在迎接offer头像 粗心的肱二头肌在迎接offer
import java.util.*;
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] x1 = new int[n];
        int[] y1 = new int[n];
        int[] x2 = new int[n];
        int[] y2 = new int[n];
        for (int i = 0; i < n; i++)
            x1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            y1[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            x2[i] = in.nextInt();
        for (int i = 0; i < n; i++)
            y2[i] = in.nextInt();
        int result = 0;
        int temp = 0;
        // 遍历所有左下焦点（包括矩形延长线，统计每个焦点在多少个矩形内部，计算最大值）
        for (int x : x1){
            for (int y : y1) {
                // (x,y)为可能的焦点
                // 遍历所有矩形
                for (int i = 0; i < n; i++) {
                    // 如果交点在内部
                    if (x >= x1[i] && x <= x2[i] && y >= y1[i] && y <= y2[i]) {
                        // 在内部的交点不能与该矩形右上重合
                        if (x == x2[i] && y == y2[i] )
                            continue;
                        temp += 1;
                    }
                }
                if (temp > result) {
                    result = temp;
                }
                temp = 0;
            }
        }
        System.out.println(result);
    }
}
发表于 2020-02-25 21:19:04 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int x1[n],y1[n],x2[n],y2[n];
    for(int i=0;i<n;i++)
        cin>>x1[i];
    for(int i=0;i<n;i++)
        cin>>y1[i];
    for(int i=0;i<n;i++)
        cin>>x2[i];
    for(int i=0;i<n;i++)
        cin>>y2[i];
    int cnt = 0, s = 0;
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            for(int k=0;k<n;k++)
                if(x1[i]>=x1[k] && x1[i]<x2[k] && y1[j]>=y1[k] && y1[j]<y2[k])
                    cnt++;
            s = max(s, cnt);
            cnt = 0;
        }
    }
    cout<<s<<endl;
    return 0;
}

发表于 2019-09-24 00:00:59 回复(0)
C/C++
Andrew_Y头像 Andrew_Y
看了很多答案，发现有些地方解释的不是很清楚，所以再提交一份我个人认为还算清楚的答案。首先对于矩形相交情况可分为以下4种（分类可能并不严格）：
1.两矩形角落部分相交
2.两矩形上下边部分相交或者左右边部分相交
3.一矩形被另外一矩形包含
4.两矩形十字相交，或者斜十字相交
可以大概画图辅助思考一下，如果几个矩形重叠，则必然有一个边角点，或者相交点同时在这几个矩形的范围内（比较直观的一种总结）。
以下是代码部分： 
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main()
{
    int res=0;
    int n;
    cin>>n;
    vector<int> x1(n);
    vector<int> y1(n);
    vector<int> x2(n);
    vector<int> y2(n);
    vector<int> x(2*n);
    vector<int> y(2*n);
    for(int i=0;i<n;i++)
    {
        cin>>x1[i];
        x[i]=x1[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>y1[i];
        y[i]=y1[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>x2[i];
        x[n+i]=x2[i];
    }
    for(int i=0;i<n;i++)
    {
        cin>>y2[i];
        y[n+i]=y2[i];
    }
    //总结所有矩形相交的情况，可以通过某一矩形的的边角点或者某一矩形和另外一矩形的交点
    //在几个矩形范围内来计量重叠矩形个数
    for(int i=0;i<2*n;i++)
        for(int j=0;j<2*n;j++)
        {
            int tmp=0;
            //去掉无意义的射线相交点，虽然不去掉也不会影响结果，但终究是无意义的情况
            if(!(x1[i%n]<=x[i]&&x[i]<=x2[i%n]&&y1[i%n]<=y[j]&&y[j]<=y2[i%n]))
                continue;
            //遍历所有矩形，看我们列举出的点最多被几个矩形包含
            for(int k=0;k<n;k++)
            {
                //这里只有一个方向是包含的，因为对于边界和角落相交并不属于矩形重叠
                if(x1[k]<=x[i]&&x[i]<x2[k]&&y1[k]<=y[j]&&y[j]<y2[k])
                    tmp++;
            }
            res=max(res,tmp);
        }
    cout<<res;
}


发表于 2019-09-15 22:00:39 回复(2)
only_唯头像 only_唯 
#include<iostream>
#include<vector>
using namespace std;

void solver(){
    int n;
    cin >> n;
    vector<int> x1(n,0);//x1,x2表示左下角的点的横纵坐标
    vector<int> x2(n,0);
    vector<int> y1(n,0);//y1,y2表示左下角的点的横纵坐标
    vector<int> y2(n,0);
    vector<int> a(2*n,0);//存储所有的横坐标
    vector<int> b(2*n,0);//存储左右的纵坐标
    for(int i = 0; i < n; i++) {
        cin >> x1[i];
        a[i] = x1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> y1[i];
        b[i] = y1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> x2[i];
        a[i+n] = x1[i];
    }
    for(int i = 0; i < n; i++) {
        cin >> y2[i];
         b[i+n] = y1[i];
    }
    int ans = 0;
    //遍历所有横纵坐标的可能组合，判断该点位于多少矩形内，则对应的矩形互相重叠
    for(int x =0;x<2*n;x++) {
        for(int y=0;y<2*n ;y++) {
            int cnt = 0;
            for(int i = 0; i < n; i++) {
                //包含左下角坐标的等号是有可能两个矩阵完全重合
                if(x1[i] <= a[x] && y1[i] <= b[y] && x2[i] > a[x] && y2[i] > b[y]) 
                    cnt++;
            }
            ans = max(ans, cnt);
        }
    }
    cout << ans << endl;
}

int main(){
    solver();
    return 0;
}

发表于 2019-07-27 16:53:37 回复(1)
calabash_boy头像 calabash_boy
对n个点用相交关系建图，求最大团。。。
#include<bitset>
#include<stdio.h>
using namespace std;
const int maxn = 50+5;
bitset<maxn> E[maxn];
int x1[maxn],y1[maxn],x2[maxn],y2[maxn];
inline void addEdge(int x,int y){
    E[x].set(y);
    E[y].set(x);
}
bool in(int xx,int yy,int w){
    if (xx>x1[w]&&xx<x2[w]&&yy>y1[w]&&yy<y2[w])return true;
    else return false;
}

bool check(int x,int y){
    if (x1[x]>=x1[y]&&y1[x]>=y1[y]&&x1[x]<x2[y]&&y1[x]<y2[y]||x2[x]<=x2[y]&&y2[x]<=y2[y]&&x2[x]>x1[y]&&y2[x]>y1[y]||x1[x]>=x1[y]&&y2[x]<=y2[y]&&x1[x]<x2[y]&&y2[x]>y1[y]||x2[x]<=x2[y]&&y1[x]>=y1[y]&&x2[x]>x1[y]&&y1[x]<y2[y]||x1[x]>=x1[y]&&x2[x]<=x2[y]&&y1[x]<=y2[y]&&y2[x]>=y1[y])return true;
    else return false;
}
int n;
int ans ;
void dfs(int dep,bitset<maxn> status){
    ans = max(ans,(int)status.count());
    if (dep==n+1)return;
    if (ans>=status.count()+n-dep+1)return;
    bitset<maxn> now1=status;
    bitset<maxn> now2 = status;
    dfs(dep+1,now2);
    if (status==(status&E[dep])){
        now1.set(dep);
        dfs(dep+1,now1);
    }
}
int main(){
  //  freopen("input.in","r",stdin);
    while (scanf("%d",&n)!=EOF&&n){
        for (int i=1;i<=n;i++){
            E[i].reset();
        }
        for (int i=1;i<=n;i++){
            scanf("%d",x1+i);
        }
        for (int i=1;i<=n;i++){
            scanf("%d",y1+i);
        }
        for (int i=1;i<=n;i++){
            scanf("%d",x2+i);
        }
        for (int i=1;i<=n;i++){
            scanf("%d",y2+i);
        }
        for (int i=1;i<=n;i++){
            for (int j=1;j<=n;j++){
                if (i==j)continue;
                if (check(i,j))addEdge(i,j);
            }
        }
        ans=0;
        bitset<maxn> status;
        status.reset();
        dfs(1,status);
        printf("%d\n",ans);
    }
}
编辑于 2018-04-29 17:57:03 回复(0)
C/C++
mankuaa头像 mankuaa
#include <iostream>
#include <string>
#include <vector>
#include<algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> x1(n), y1(n), x2(n), y2(n);
    for (int i = 0; i !=n; i++)
        cin>>x1[i];
    for (int i = 0; i != n; i++)
        cin >> y1[i];
    for (int i = 0; i != n; i++)
        cin >> x2[i];
    for (int i = 0; i != n; i++)
        cin >> y2[i];

    vector<int> x = x1,y=y1;
    for (int i = 0; i != n; i++)
    {
        x.push_back(x2[i]);
        y.push_back(y2[i]);
    }
    sort(x.begin(), x.end());
    sort(y.begin(), y.end());

    vector<double>xx(2*n-1),yy(2*n-1);
    for (int j = 0; j != 2 * n - 1; j++)
    {
        xx[j] = (x[j] + x[j + 1]) / 2.0;
        yy[j] = (y[j] + y[j + 1]) / 2.0;
    }

    int max = 0;
    for(int i=0; i != 2 * n-1; i++)
        for (int j = 0; j != 2 * n - 1; j++)
        {
            int num = 0;
            for (int k = 0; k != n; k++)
            {
                if (x1[k] < xx[i] && xx[i] < x2[k] && y1[k] < yy[j] && yy[j] < y2[k])
                    num++;
            }
            if (num > max)
                max = num;
        }
    cout << max;
    system("pause");
    return 0;
}
  
发表于 2018-04-08 10:49:39 回复(0)
霍七头像 霍七

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <vector>
#include <cstring>
using namespace std;
struct Rectangle
{
    int x1, x2, y1, y2;
};
int main()
{
    int n; cin >> n;
    Rectangle *rect = new Rectangle[n];
    int *x = new int[n * 2];
    int *y = new int[n * 2];
    for (int i = 0; i < n; i++) {
        cin >> rect[i].x1;
        x[i] = rect[i].x1;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].y1;
        y[i] = rect[i].y1;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].x2;
        x[i + n] = rect[i].x2;
    }
    for (int i = 0; i < n; i++) {
        cin >> rect[i].y2;
        y[i + n] = rect[i].y2;
    }
    sort(x, x + 2 * n);
    sort(y, y + 2 * n);
    vector<int> vectorx;
    vector<int> vectory;
    vectorx.push_back(x[0]);
    vectory.push_back(y[0]);
    for (int i = 1; i < 2 * n; i++) {
        if (x[i] != x[i - 1]) {
            vectorx.push_back(x[i]);
        }
        if (y[i] != y[i - 1]) {
            vectory.push_back(y[i]);
        }
    }
    delete[] x;
    delete[] y;
    unordered_map<int, int> myMapx;
    unordered_map<int, int> myMapy;
    for (int i = 0; i < vectorx.size(); i++) {
        myMapx[vectorx[i]] = i;
    }
    for (int i = 0; i < vectory.size(); i++) {
        myMapy[vectory[i]] = i;
    }
    int **map = new int*[vectorx.size()];
    for (int i = 0; i < vectorx.size(); i++) {
        map[i] = new int[vectory.size()];
        memset(map[i], 0, sizeof(int)*vectory.size());
    }
    for (int i = 0; i < n; i++) {
        for (int j = myMapx[rect[i].x1]; j < myMapx[rect[i].x2]; j++) {
            for (int k = myMapy[rect[i].y1]; k < myMapy[rect[i].y2]; k++) {
                map[j][k] += 1;
            }
        }
    }
    int maxNum = 0;
    for (int i = 0; i < vectorx.size(); i++) {
        for (int j = 0; j < vectory.size(); j++) {
            maxNum = max(maxNum, map[i][j]);
        }
    }
    for (int i = 0; i < vectorx.size(); i++) {
        delete[] map[i];
    }
    delete[] map;
    delete[] rect;
    cout << maxNum;
    return 0;
}
发表于 2018-03-28 19:15:18 回复(0)
努力努力！头像 努力努力！
有一个点有连续的两个空格 结果我split(' ')被坑了   输入好好做啊
发表于 2018-03-28 17:53:53 回复(1)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 高级结构 穷举 网易 2019 数学 Java工程师
来自：网易2019实习生招聘...
上传者：小小
难度：
56条回答 33949浏览

热门推荐

通过挑战的用户

查看代码

相关试题

矩形重叠

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号