[POJ 3168] Barn Expansion【扫描线】

  • 2018-01-08
  • 0
  • 0

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

Line 1: A single integer that is the number of barns that can be expanded.

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

USACO 2005 December Gold

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;
}

评论

还没有任何评论,你来说两句吧



常年不在线的QQ:
49750

不定期更新的GitHub:
https://github.com/Darkleafin


OPEN AT 2017.12.10

如遇到代码不能正常显示的情况,请刷新页面。
If the code cannot be displayed normally, please refresh the page.


发现一个优美的网站:
https://visualgo.net/en
















- Theme by Qzhai