这题的算法其实是非常简单的。
由于没有overlap，所以只用考虑有公共边与公共点的情况就行了。
先考虑平行与y轴的公共边，
把所有的数按x排序，之后只考虑x相同的边。
随便使用一种扫描的方法来判断若干个区间是否有公共部分就行了。
具体的可以看代码。
考虑平行与x轴的公共边同理。
为了简化，可以把公共点理解为长度为0的公共边，这样也一并解决了。

关键就是排序。
我拿出了我喜欢的屡试不爽的经典的quicksort的写法：
#define Swap(u,v) {t=rank[u];rank[u]=rank[v];rank[v]=t;}
void qs(int b,int e){if (b>=e)return;
	static int j,t;
	Swap(b,(b+e)>>1);
	for (int i=j=b+1;i<=e;i++)if (A[rank[i]]<A[rank[b]] ||
		A[rank[i]]==A[rank[b]] && (B[rank[i]]<B[rank[b]] || B[rank[i]]==B[rank[b]] && (i&1))){
			Swap(i,j);
			j++;
		}
	--j;
	Swap(b,j);
	qs(b,j-1);qs(j+1,e);
}
这里加入了不少抗恶心数据（例如已经排好序的，或者全都一样的）的方法，
所以还没有什么排序题能卡住它。
然而，TLE了？！
出于对自己扫描能力的信任，我判断是快排导致了超时。
然而，在百度上搜索这题，发现有人是用快排过的。
（http://old.blog.edu.cn/user4/bitacmer/archives/2007/1723278.shtml）
这是怎么回事？
再仔细看了看他的代码，使用的是库函数，其他地方倒与我的没有两样。
那为什么快速排序也能一个t一个A呢？
我开始怀疑自己喜欢的经典快排的常数，并且猜测是由于rank的使用以及
坑恶心导致的。

AC才是王道。我祭出了排序的终极武器：基数排序。
void rs(int n){
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[B[i]&1023]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[B[rank[i]]&1023]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[B[i]>>10]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[B[rank[i]]>>10]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[A[i]&1023]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[A[rank[i]]&1023]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[A[i]>>10]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[A[rank[i]]>>10]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
}
实践证明，过了，并且速度比那个快排的人快2倍。
我没有使用计数排序的原因是担心数据范围太大（0~1000000），
如果case数量达到100个以上恐怕吃不消。
这题让我见识了：写快排也有好坏之分，并不是每个人的排序都一样好。

示例代码：
void rs(int n){
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[B[i]&1023]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[B[rank[i]]&1023]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[B[i]>>10]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[B[rank[i]]>>10]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[A[i]&1023]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[A[rank[i]]&1023]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
	memset(cnt,0,sizeof(cnt));
	for (int i=0;i<n;i++)cnt[A[i]>>10]++;
	for (int i=1;i<1024;i++)cnt[i]+=cnt[i-1];
	for (int i=n-1;i>=0;i--)buf[--cnt[A[rank[i]]>>10]]=rank[i];
	memcpy(rank,buf,n*sizeof(rank[0]));
}


	scanf("%d",&N);
	for (int i=0;i<N;i++){
		scanf("%d %d %d %d",X1+i,Y1+i,X2+i,Y2+i);
		flag[i]=1;
	}
	for (int i=0;i<N;i++){
		A[i]=X1[i];B[i]=Y1[i];E[i]=Y2[i];I[i]=i;
		A[i+N]=X2[i];B[i+N]=Y1[i];E[i+N]=Y2[i];I[i+N]=i;
	}
	for (int i=0;i<N+N;i++)rank[i]=i;
	rs(N+N);
	for (int i=0;i<N+N;i=k){
		k=i;
		while (k<N+N && A[rank[i]]==A[rank[k]])k++;
		low=-1;
		for (int j=i;j<k;j++){
			if (j!=k-1 && E[rank[j]]>=B[rank[j+1]])flag[I[rank[j]]]=0;
			if (B[rank[j]]<=low)flag[I[rank[j]]]=0;
			if (low<E[rank[j]])low=E[rank[j]];
		}
	}
	for (int i=0;i<N;i++){
		A[i]=Y1[i];B[i]=X1[i];E[i]=X2[i];I[i]=i;
		A[i+N]=Y2[i];B[i+N]=X1[i];E[i+N]=X2[i];I[i+N]=i;
	}
	for (int i=0;i<N+N;i++)rank[i]=i;
	rs(N+N);
	for (int i=0;i<N+N;i=k){
		k=i;
		while (k<N+N && A[rank[i]]==A[rank[k]])k++;
		low=-1;
		for (int j=i;j<k;j++){
			if (j!=k-1 && E[rank[j]]>=B[rank[j+1]])flag[I[rank[j]]]=0;
			if (B[rank[j]]<=low)flag[I[rank[j]]]=0;
			if (low<E[rank[j]])low=E[rank[j]];
		}
	}
	ret=0;
	for (int i=0;i<N;i++)ret+=flag[i];
	printf("%d\n",ret);

• 其实那个快排是有killer数据的： (264) fanhqme 2010-08-27 17:27:06
• http://www.bootsspaschersoldes.info ugg pas cher (1134) Unpanvary 2012-12-13 07:47:35