2785.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

 #include<cstdio> 
#include<iostream>
#include<algorithm>
using namespace std;
int a[4002][4];
int b1[4001*4001] ,b2[4001*4001];
int n;
_int64 s ; 
 
main()
{
	int i,j;
	
//	freopen("1.in","r",stdin);
	scanf("%d",&n);
	for(i=0;i<n;i++)
		for(j=0;j<4;j++)
			scanf("%d",&a[i][j]); 
		int t=0;
		for(i=0;i<n;i++)
            for(j=0;j<n;j++)
			{	b1[t]=a[i][0]+a[j][1];
			b2[t++]=-(a[i][2]+a[j][3]);}
	   
			sort(b1,b1+t);
		    sort(b2,b2+t); 
		 j=0;
			for(i=0;i<t;i++) 
			{  
				while(j<t&&b2[j]<b1[i])  	
					j++;
				
				while(j<t&&b2[j]==b1[i])
				{ 
					s++;j++;
				}
				if(j==t) j--;
				while(j>0&&i+1<t&&b2[j]>=b1[i+1])
					j--; 
			}
			 
		printf("%I64d\n",s);

}