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.
约翰有N(1≤N≤25000)个矩形牛棚，它们的墙均与坐标轴平行，而且其坐标在[o，1061范围内．任意两个牛棚不重叠，但可能会有公共的墙． 由于约翰的奶牛持续增加，他不得不考虑扩张牛棚．一个牛棚可以扩张，当且仅当它的四边均不与其它牛棚接触．如果两个牛棚有一个公共角，那它们均是不可扩张的．统计有多少牛棚可以扩张．* 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).
第1行输入N，之后N行每行输入一个牛棚的左下角和右上角坐标． 输出说明* Line 1: A single integer that is the number of barns that can be expanded.
输出可扩张的牛棚数．
Gold
[ Submit][ Status][ Discuss]
大力扫描线 防止一些麻烦的情况就从左往右和从右往左都做一遍
把一个矩形拆成两个部分 (l,d,u) (r,d,u) 表示横坐标为l/r 纵坐标从d到u的两个线段
然后按照横坐标排序 如果横坐标相等则插入的优先
然后先处理新插入的情况 这题矩形有交只有两种情况 上下相邻和左右相邻
上下相邻比较好处理
开两个个O(M)的数组 M是坐标大小
f[i][0]表示以i为下端点的矩形的号码
f[i][1]表示以i为上端点的矩形的号码
因为矩形不存在重叠等情况 所以在任何时刻他的值是唯一的
所以可以插入的时候查询一下那两个端点就可以了
左右情况可以开两个O(M)树状数组
第一个F1(x) 记录下端点为x的前缀和
第二个F2(x) 记录上端点为x的前缀和
如果一个矩形和其他的有左右相邻的话
那么如果 F1(u)-F2(d) > 0就表示有相邻（稍微YY一下比较显然）
这样开一个bool数组记录一下是否已经不行了 最后答案就是bool数组里为0的个数
代码：
1 #include<set> 2 #include<cstdio> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 #define Rep(i,x,y) for(int i=x;i<y;++i) 7 #define For(i,x,y) for(int i=x;i<=y;++i) 8 using namespace std; 9 const int N = 3e5+5; 10 const int M = 1e6+5; 11 struct data{ 12 int x,u,d,id; 13 bool kd; 14 bool operator < (const data&b) const{ 15 return x<b.x||x==b.x&&kd<b.kd; 16 } 17 }a[N]; 18 struct bit{ 19 int c[M]; 20 #define lowbit(x) (x&-x) 21 void insert(int x){ 22 for(int i=x;i<M;i+=lowbit(i)) 23 c[i]++; 24 } 25 void erase(int x){ 26 for(int i=x;i<M;i+=lowbit(i)) 27 c[i]--; 28 } 29 int query(int x){ 30 if(!x) return 0; 31 int res=0; 32 for(int i=x;i;i-=lowbit(i)) 33 res+=c[i]; 34 return res; 35 } 36 void init(){ 37 memset(c,0,sizeof(c)); 38 } 39 }T1,T2; 40 int cnt; 41 int n; 42 bool nok[N]; 43 int f[M][2]; 44 void del(int i){ 45 T1.erase(a[i].d); 46 T2.erase(a[i].u+1); 47 f[a[i].u][0]=0; 48 f[a[i].d][1]=0; 49 } 50 void INS(int i){ 51 f[a[i].u][0]=a[i].id; 52 f[a[i].d][1]=a[i].id; 53 T1.insert(a[i].d); 54 T2.insert(a[i].u+1); 55 } 56 void ins(int l,int r){ 57 For(i,l,r) 58 INS(i); 59 For(i,l,r){ 60 del(i); 61 if(f[a[i].u][1]){ 62 nok[a[i].id]=1; 63 nok[f[a[i].u][1]]=1; 64 } 65 if(f[a[i].d][0]){ 66 nok[a[i].id]=1; 67 nok[f[a[i].d][0]]=1; 68 } 69 if(T1.query(a[i].u)-T2.query(a[i].d)>0) nok[a[i].id]=1; 70 INS(i); 71 } 72 } 73 int main(){ 74 scanf("%d",&n); 75 For(i,1,n){ 76 int l,r,u,d; 77 scanf("%d%d%d%d",&l,&d,&r,&u); 78 ++l;++r;++d;++u; 79 a[++cnt]=(data){l,u,d,i,0}; 80 a[++cnt]=(data){r,u,d,i,1}; 81 } 82 n<<=1; 83 sort(a+1,a+n+1); 84 for(int i=1;i<=n;){ 85 int l=i;int r=i; 86 for(;r<=n&&a[r].x==a[l].x&&a[r].kd==0;++r); 87 ins(l,r-1); 88 for(;r<=n&&a[r].kd==1;++r) 89 del(r); 90 i=r; 91 } 92 memset(f,0,sizeof(f)); 93 T1.init(); 94 T2.init(); 95 for(int i=n;i;){ 96 int r=i;int l=i; 97 for(;l>0&&a[l].x==a[r].x&&a[l].kd==1;--l); 98 ins(l+1,r); 99 for(;l>0&&a[l].kd==0;--l) del(l); 100 i=l; 101 } 102 int res=0; 103 For(i,1,n/2) if(!nok[i]) ++res; 104 cout<<res<<endl; 105 return 0; 106 }
转载于:https://www.cnblogs.com/rwy233/p/7061910.html
