我是靠谱客的博主 乐观摩托,这篇文章主要介绍poj3168(扫描线),现在分享给大家,希望可以做个参考。

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/* 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(扫描线)内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(99)

评论列表共有 0 条评论

立即
投稿
返回
顶部