2183910_ac_3420ms_49048k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 39 行

#include<cstdio>
#include<algorithm>
 using namespace std;
 
 
 int N;
 int A[4000],B[4000],C[4000],D[4000];
 int AB[4000*4000],CD[4000*4000];
 int main(){
	int i,j,p,cnt=0;
 	while(scanf("%d",&N)==1){
 		for(i=0;i<N;++i)
			scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
 		
		for(i=0;i<N;++i){
 			for(j=0;j<N;++j){
 				AB[N*i+j]=A[i]+B[j];
 				CD[N*i+j]=C[i]+D[j];
 			}
 		}
 
 		sort(AB,AB+N*N);
 		sort(CD,CD+N*N);
 		cnt=0;
 		
 		for(i=0,j=N*N-1;i<N*N;++i){
 			if(i>0&&AB[i]==AB[i-1])
 				cnt+=p;
 			else{
 				p=0;
 				while(j>=0&&-AB[i] < CD[j]) --j;
 				while(j>=0&&-AB[i] == CD[j]) ++cnt,++p,--j;
 			}
 		}
 		
 		printf("%d\n",cnt);
 	}
 	return 0;
 }