Entrenamiento IOI - Etapa #2 - Problem: 4 Values whose Sum is 0 - Judge: ACM-ICPC Live Archive - 15/12/2014 - Puntaje: 100% (AC) - Meet In The Middle + Barrido.

gistfile1.cpp

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#define all(v) v.begin(), v.end()
#define ver(x) cout<<#x<<": "<<x<<"\n";
#define verP(x) cout<<#x<<": "<<*x<<"\n";
#define name(x) cout<<#x<<" \n";
#define MAXSZ 16000002
using namespace std;
typedef long long int lli;
int N;
int numX[MAXSZ]={0}, numY[MAXSZ]={0};
int X[MAXSZ], Y[MAXSZ];
int pX = 0, pY = 0;
lli Answer = 0;
void printArray(int* array, int tam){
	int i;
	cout<<"\n";
	name(array);
	for(i=0; i<tam; ++i){
		cout<<array[i]<<" ";
	}
	cout<<"\n";
}
void subsets(int* A, int* B, int* C, int*D){
	int i, j;
	for(i=0; i<N; ++i){
		for(j=0; j<N; ++j){
			X[pX++] = A[i]+B[j];
		}
	}
	for(i=0; i<N; ++i){
		for(j=0; j<N; ++j){
			Y[pY++] = (C[i]+D[j])*-1;
		}
	}
	sort(X,X+pX);
	sort(Y,Y+pY);
}
void suprimeEquals(){
	int i, j, p;
	p = 0;
	numX[p] = 1;
	for(i=1; i<pX; ++i){
		if(X[i]!=X[i-1]){
			++p;
			X[p]=X[i];
			numX[p] = 1;
		} else {
			++numX[p];
		}
	}
	pX=p+1;
	p = 0;
	numY[p] = 1;
	for(i=1; i<pY; ++i){
		if(Y[i]!=Y[i-1]){
			++p;
			Y[p]=Y[i];
			numY[p] = 1;
		} else {
			++numY[p];
		}
	}
	pY=p+1;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
    int T;
	int i,j,k,p,q;
	scanf("%d", &T);
	while(T-- > 0){
		memset(numX,0,sizeof(numX));
		memset(numY,0,sizeof(numY));
		memset(X,0,sizeof(X));
		memset(Y,0,sizeof(Y));
		pY = 0;
		pX = 0;
		Answer = 0;
		scanf("%d",&N);
		int A[N],B[N],C[N],D[N];
		for(i=0; i<N; ++i){
			scanf("%d %d %d %d",&A[i],&B[i],&C[i],&D[i]);
		}
		subsets(A,B,C,D);
		suprimeEquals();
		// printArray(X,pX);
		// printArray(Y,pY);
		i = j = 0;
		while(i<pX && j<pY){
			if( (X[i]-Y[j]) == 0 ){
				Answer += (lli)(numX[i]*numY[j]);
				++i; ++j;
			} else if(X[i]>Y[j]){
				++j;
			} else {
				++i;
			}
		}
		printf("%lld\n",Answer);
		if(T){
            		printf("\n");
        	}
	}
	return 0;
}