[ SOLUCIÓN MEJORADA ] - 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 <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 X[MAXSZ], Y[MAXSZ];
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";
}
int main(){
	int T;
	int i,j,k,p,q;
	scanf("%d",&T);
	while(T-- > 0){
		Answer = 0;
		scanf("%d",&N);
		int A[N],B[N],C[N],D[N];
		int pX = 0, pY = 0;
		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){
				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);
		vector<int> v(Y, Y+pY);
		vector<int>::iterator low, up;
		int a = 0, b = 0;
		for(i=0; i<pX; ++i){
			low = lower_bound(all(v), X[i]);
			a = (low - v.begin());
			up = upper_bound(all(v), X[i]);
			b = (up - v.begin());
			Answer += (b-a);
		}
		printf("%lld\n",Answer);
		if(T){
			printf("\n");
		}
	}
	return 0;
}