题目链接：

id=3168">POJ 3168 Barn Expansion

题意：抽象出来就是给出n个矩形的坐标是（左下角和右上角的坐标，矩形的边都是平行x,y轴），问有几个矩形和其它矩形没有接触（仅仅存在边接触或者点接触，不存在有公共面积）。

思路：把边分成两类，平行x轴和平行y轴。对边进行排序。然后for一遍推断是否有相交就可以

AC代码：

#include <stdio.h>

#include <vector>

#include <map>

#include <set>

#include <algorithm>

using namespace std;

struct node {

    int mark;

    int d,xx,yy;

    node() {}

    node(int _d,int _xx,int _yy,int _mark) {

        d=_d,xx=_xx,yy=_yy,mark=_mark;

    }

};

vector<node> sx,sy;

bool vis[25010];

bool cmp(node a,node b) {

    if(a.d!=b.d) return a.d<b.d;

    else if(a.xx!=b.xx) return a.xx<b.xx;

    else return a.yy<b.yy;

}

int main() {

    int n;

    int i,j,k;

	int a,b,c,d;

    while(scanf("%d",&n)!=EOF) {

        sx.clear();

        sy.clear();

		memset(vis,false,sizeof vis);

        for(i=0; i<n; i++) {

            scanf("%d %d %d %d",&a,&b,&c,&d);

            sy.push_back(node(b,a,c,i));

            sy.push_back(node(d,a,c,i));

            sx.push_back(node(a,b,d,i));

            sx.push_back(node(c,b,d,i));

        }

        int sz1,sz2;

        sz1=sy.size();

        sz2=sx.size();

        sort(sx.begin(),sx.end(),cmp);

        sort(sy.begin(),sy.end(),cmp);

        //竖 y<yy

		int up;

		up=sy[0].yy;

        for(i=1;i<sz1;i++){

			if(sy[i-1].d == sy[i].d){

				if(up >= sy[i].xx){

					vis[sy[i].mark]=vis[sy[i-1].mark]=true;

				}

			}

			else up=sy[i].yy;

			up=max(sy[i].yy,up);

        }

		up=sx[0].yy;

		for(i=1;i<sz2;i++){

			if(sx[i-1].d == sx[i].d){

				if(up >= sx[i].xx){

					vis[sx[i].mark]=vis[sx[i-1].mark]=true;

				}

			}

			else up=sx[i].yy;

			up=max(sx[i].yy,up);

        }

		int ans=0;

		for(i=0;i<n;i++){

			if(!vis[i]) ans++;

		}

		printf("%d\n",ans);

    }

    return 0;

}

/*

5

0 2 2 7

3 5 5 8

4 2 6 4

6 1 8 6

0 0 8 1

4

2 1 3 2

2 2 3 3

3 3 4 4

4 1 5 2

9

0 0 1 1

1 0 2 1

2 0 3 1

0 1 1 2

1 1 2 2

2 1 3 2

0 2 1 3

1 2 2 3

2 2 3 3

6

0 2 2 7

3 5 5 8

4 2 6 4

6 1 8 6

0 0 8 1

4 5 5 6

3

1 1 6 6

6 2 7 3

6 5 8 7

*/