题链：http://poj.org/problem?
id=3168
Barn Expansion
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 2087 | Accepted: 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.
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).
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.
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 4
4 1 0 0 0 0 1 0
0 0 0 1 0 1 0 0
0 2 1 1 3 0 4 0
0 0 0 4 1 1 1 0
*/