[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;
}
发表评论