题链：?id=3168
Barn Expansion
Time Limit:1000MSMemory Limit:65536K
Total Submissions:2087Accepted:544
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, NLines 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
50 2 2 73 5 5 84 2 6 46 1 8 60 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.
题意：给若干个矩形，直接只有接触，没有重叠，计算出有多少矩形是不和其他矩形有接触。
做法：
把两条横向边和纵向边分解开来。各自存入数组 hh，和ss。
然后排序。以横向为例。先按高度排序，高度相同的 按左边的坐标从小到大排序。
然后for一遍，，注意下判断重合时，之前的那个矩形pre也要标记成有接触。#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#include <malloc.h>#include <ctype.h>#include <math.h>#include <string>#include <iostream>#include <algorithm>using namespace std;#include <stack>#include <queue>#include <vector>#include <deque>#include <set>#include <map>struct point {int s,x,id;//下 左 负 int z,y;point(){}point(int _x,int _s,int _z,int _y,int _id){ s=_s,x=_x,z=_z,y=_y,id=_id;}}; point hh[1000010]; //放横的point ss[1001000];int has[26000];int cmph(point a,point b){ if(a.s!=b.s)return a.s<b.s;return a.z<b.z;} int cmps(point a,point b) {if(a.z!=b.z)return a.z<b.z;return a.x<b.x;}int main(){int n;while(scanf("%d",&n)!=EOF){memset(has,0,sizeof has); int h=0;int s=0; for(int i=0;i<n;i++) {int l,x,r,sh;scanf("%d%d",&l,&x);scanf("%d%d",&r,&sh);hh[h++]=point(x,x,l,r,i);hh[h++]=point(sh,sh,l,r,i);ss[s++]=point(x,sh,l,l,i);ss[s++]=point(x,sh,r,r,i); } sort(hh,hh+h,cmph); sort(ss,ss+s,cmps); int z,y; int pre; for(int i=0;i<h;i++) {if(i==0){z=hh[i].z;y=hh[i].y;pre=hh[i].id;}else if(hh[i-1].s==hh[i].s){if(hh[i].z<=y) //在之前的范围内{has[pre]=1;has[hh[i].id]=1;}else //不在之前范围内{z=hh[i].z;y=hh[i].y;pre=hh[i].id;}if(hh[i].y>y)//扩展右边y=hh[i].y;}else//不在一个高度时{z=hh[i].z;y=hh[i].y;pre=hh[i].id;} } int xi,sh; for(int i=0;i<=s;i++) {// printf("x%d s%d l%d id%d\n",ss[i].x,ss[i].s,ss[i].z);if(i==0){xi=ss[i].x;sh=ss[i].s;pre=ss[i].id;}else if(ss[i-1].y==ss[i].y){if(ss[i].x<=sh){has[ss[i].id]=1;has[pre]=1;}else{xi=ss[i].x;sh=ss[i].s;pre=ss[i].id;}if(ss[i].s>sh)sh=ss[i].s;}else{xi=ss[i].x;sh=ss[i].s;pre=ss[i].id;} } int ans=0; for(int i=0;i<n;i++) {if(has[i]){// printf("id%d ",i);ans++;} } printf("%d\n",n-ans); }return 0; }/*8 44 1 0 0 0 0 1 00 0 0 1 0 1 0 00 2 1 1 3 0 4 00 0 0 4 1 1 1 0*/
版权声明：本文为博主原创文章，未经博主允许不得转载。
我无所事事的度过了今天，是昨天死去的人们所期望的明天。
