[POJ 3168] Barn Expansion【扫描线】
Problem:
Time Limit: 1000MS | Memory Limit: 65536K |
Description
Farmer John has N (1 <= N <= 25,000) rectangular barns on his farm, all with sides parallel to the X and Y axes and integer corner coordinates in the range 0..1,000,000. These barns do not overlap although they may share corners and/or sides with other barns.
Since he has extra cows to milk this year, FJ would like to expand some of his barns. A barn has room to expand if it does not share a corner or a wall with any other barn. That is, FJ can expand a barn if all four of its walls can be pushed outward by at least some amount without bumping into another barn. If two barns meet at a corner, neither barn can expand.
Please determine how many barns have room to expand.
Input
Line 1: A single integer, N
Lines 2..N+1: Four space-separated integers A, B, C, and D, describing one barn. The lower-left corner of the barn is at (A,B) and the upper right corner is at (C,D).
Output
Sample Input
5 0 2 2 7 3 5 5 8 4 2 6 4 6 1 8 6 0 0 8 1
Sample Output
2
Hint
Explanation of the sample:
There are 5 barns. The first barn has its lower-left corner at (0,2) and its upper-right corner at (2,7), and so on.
Only two barns can be expanded --- the first two listed in the input. All other barns are each in contact with at least one other barn.
Source
Solution:
这道题是较为简单的扫描线算法题(因为没有用到线段树 .囧/)。
水平线段和竖直线段需要分开处理来判断重合情况,但是道理基本相同,这里只讨论竖直线段的重合情况。
首先要对竖直线段按从左到右,底端点从下到上的顺序排序。
每次可能重合的一定是横坐标相同的线段,而且其底端点纵坐标一定小于该横坐标下当前最高的顶端点纵坐标。横坐标改变时需要将最高纵坐标重置为极小值。
Code: O(nlogn) [1720K, 313MS]
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; int N; bool ex[25002]; struct Segment{ int l, r, h; int id; inline bool operator < (const Segment &seg2) const { if(h == seg2.h) return l < seg2.l; return h < seg2.h; } } hor[50002], ver[50002]; int main(){ scanf("%d", &N); for(register int i = 1; i <= N; i++){ int A, B, C, D; scanf("%d%d%d%d", &A, &B, &C, &D); hor[i].h = A, hor[i].l = B, hor[i].r = D, hor[i].id = i; hor[N + i].h = C, hor[N + i].l = B, hor[N + i].r = D, hor[N + i].id = i; ver[i].h = B, ver[i].l = A, ver[i].r = C, ver[i].id = i; ver[N + i].h = D, ver[N + i].l = A, ver[N + i].r = C, ver[N + i].id = i; } N <<= 1, sort(hor + 1, hor + N + 1), sort(ver + 1, ver + N + 1); memset(ex, 1, sizeof(ex)); int maxr = -1, id; for(register int i = 1; i < N; i++){ if(ver[i].h == ver[i + 1].h){ if(ver[i].r > maxr) maxr = ver[i].r, id = ver[i].id; if(ver[i + 1].l <= maxr) ex[ver[i + 1].id] = ex[id] = 0; } else maxr = -1; } maxr = -1; for(register int i = 1; i < N; i++){ if(hor[i].h == hor[i + 1].h){ if(hor[i].r > maxr) maxr = hor[i].r, id = hor[i].id; if(hor[i + 1].l <= maxr) ex[hor[i + 1].id] = ex[id] = 0; } else maxr = -1; } N >>= 1; int ans = 0; for(register int i = 1; i <= N; i++) if(ex[i]) ans++; printf("%d\n", ans); return 0; }
发表评论