# [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

## Code: O(nlogn) [1720K, 313MS]

```#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;

int N;
bool ex;

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, ver;

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

#### 评论

49750

https://github.com/Darkleafin

OPEN AT 2017.12.10

Please refresh the page if the code cannot be displayed normally.

https://visualgo.net/en

- Theme by Qzhai