poj3168（扫描线）

/*
translation:
给出几个长方形的位置以及边长情况，问能扩张的长方形有几个。
solution:
从上到下，从左到右扫描两边。预先对每条边排序，扫到这条边时，对其和这条边位置相同的边进行判断，是否有
重合的点。如果有，那么这两条边各自对应的长方形就不可能扩张了。
note:
*/
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 25000 + 5;
struct Interval
{
int pos, lb, ub, id;
Interval(){}
Interval(int pos, int lb, int ub, int id):pos(pos),lb(lb),ub(ub),id(id){}
bool operator < (const Interval& rhs) const {
return pos < rhs.pos || (pos == rhs.pos && lb < rhs.lb) ||
(pos == rhs.pos && lb == rhs.lb && ub < rhs.ub);
}
};
vector<Interval> vy;	//y方向上的线段
vector<Interval> vx;	//x方向上的线段
int n;
bool expand[maxn];
int main()
{
//freopen("in.txt", "r", stdin);
while(~scanf("%d", &n)) {
vy.clear();
vx.clear();
int a, b, c, d;
for(int i = 0; i < n; i++) {
scanf("%d%d%d%d", &a, &b, &c, &d);
vy.push_back(Interval(a, b, d, i));
vy.push_back(Interval(c, b, d, i));
vx.push_back(Interval(b, a, c, i));
vx.push_back(Interval(d, a, c, i));
}
sort(vx.begin(), vx.end());
sort(vy.begin(), vy.end());
for(int i = 0; i < n; i++)	expand[i] = true;
int rightPos = vx[0].ub;
for(int i = 1; i < vx.size(); i++) {
if(vx[i-1].pos == vx[i].pos) {
if(rightPos >= vx[i].lb) {
expand[vx[i].id] = expand[vx[i-1].id] = false;
}
} else {
rightPos = vx[i].ub;
}
rightPos = max(rightPos, vx[i].ub);
}
int highPos = vy[0].ub;
for(int i = 1; i < vy.size(); i++) {
if(vy[i-1].pos == vy[i].pos) {
if(highPos >= vy[i].lb) {
expand[vy[i].id] = expand[vy[i-1].id] = false;
}
} else {
highPos = vy[i].ub;
}
highPos = max(highPos, vy[i].ub);
}
int ans = 0;
for(int i = 0; i < n; i++)
if(expand[i])	ans++;
printf("%dn", ans);
}
return 0;
}

最后

以上就是乐观摩托为你收集整理的poj3168（扫描线）的全部内容，希望文章能够帮你解决poj3168（扫描线）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。