内接最大矩形,,c++
时间: 2023-08-09 19:05:24 浏览: 38
内接最大矩形问题可以使用扫描线算法进行解决。具体步骤如下:
1. 构建扫描线
将所有矩形的左右边界按照横坐标排序,作为扫描线的节点,同时记录每个节点的类型(左边界或右边界)和所属的矩形编号。
2. 扫描线遍历
从左到右遍历扫描线,维护一个高度为当前扫描线所在位置的最大矩形。遇到左边界时,将该矩形加入高度为0的线段树中;遇到右边界时,将该矩形从线段树中删除。每次更新完线段树后,更新最大矩形的面积。
3. 输出结果
遍历完扫描线后,最大矩形的面积即为所求。
以下是C++代码实现:
```c++
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 10005;
struct Rect {
int x1, y1, x2, y2;
} rect[MAXN];
struct Line {
int x, y1, y2, type;
bool operator<(const Line& l) const {
return x < l.x;
}
};
vector<int> ys;
vector<Line> lines;
struct Node {
int l, r, len, tag;
} tree[MAXN * 4];
void build(int p, int l, int r) {
tree[p].l = l;
tree[p].r = r;
tree[p].len = tree[p].tag = 0;
if (l == r) return;
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
}
void pushup(int p) {
if (tree[p].tag > 0)
tree[p].len = ys[tree[p].r] - ys[tree[p].l - 1];
else
tree[p].len = tree[p * 2].len + tree[p * 2 + 1].len;
}
void pushdown(int p) {
if (tree[p].tag) {
tree[p * 2].tag = tree[p * 2 + 1].tag = tree[p].tag;
tree[p * 2].len = ys[tree[p * 2].r] - ys[tree[p * 2].l - 1];
tree[p * 2 + 1].len = ys[tree[p * 2 + 1].r] - ys[tree[p * 2 + 1].l - 1];
tree[p].tag = 0;
}
}
void update(int p, int l, int r, int v) {
if (tree[p].l >= l && tree[p].r <= r) {
tree[p].tag += v;
pushup(p);
return;
}
pushdown(p);
int mid = (tree[p].l + tree[p].r) / 2;
if (l <= mid) update(p * 2, l, r, v);
if (r > mid) update(p * 2 + 1, l, r, v);
pushup(p);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> rect[i].x1 >> rect[i].y1 >> rect[i].x2 >> rect[i].y2;
ys.push_back(rect[i].y1);
ys.push_back(rect[i].y2);
}
sort(ys.begin(), ys.end());
ys.erase(unique(ys.begin(), ys.end()), ys.end());
for (int i = 1; i <= n; i++) {
rect[i].y1 = lower_bound(ys.begin(), ys.end(), rect[i].y1) - ys.begin() + 1;
rect[i].y2 = lower_bound(ys.begin(), ys.end(), rect[i].y2) - ys.begin() + 1;
lines.push_back({rect[i].x1, rect[i].y1, rect[i].y2, 1});
lines.push_back({rect[i].x2, rect[i].y1, rect[i].y2, -1});
}
sort(lines.begin(), lines.end());
build(1, 1, ys.size() - 1);
int ans = 0;
for (int i = 0; i < lines.size(); i++) {
if (i > 0) ans = max(ans, tree[1].len * (lines[i].x - lines[i - 1].x));
update(1, lines[i].y1, lines[i].y2 - 1, lines[i].type);
}
cout << ans << endl;
return 0;
}
```