1152

Meet in the middle  and binary search algorithm is used to solve this problem.

#include <iostream>
#include <string.h>
#include <algorithm>
#include <map>

using namespace std;

int A[4001];
int B[4001];
int C[4001];
int D[4001];

int E[16008001];
int F[16008001];

//map<int,int> mp;
struct myHash
{
	int value;
	int valueOccuredNumberOfTimes;
}FF[16008001];

int main()
{
	int t,n,x,cnt,a;
	int low,mid,high;
	int k,l;
	cin>>t;

	while(t--)
	{
		cin>>n;
		cnt=0;
		//mp.clear();
		for(int i=0;i<n;i++)
		{
			cin>>A[i]>>B[i]>>C[i]>>D[i];
		}

		k=0;
		l=0;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				E[k++]=A[i]+B[j];
				F[l++]=C[i]+D[j];
			}
		}

		sort(F,F+l);
		FF[0].value = F[0];
		FF[0].valueOccuredNumberOfTimes=1;
		int ind=0;

		for(int i=1;i<l;i++)
		{
			if(F[i]==F[i-1])
			{
				FF[ind].valueOccuredNumberOfTimes+=1;
			}
			else
			{
				ind+=1;
				FF[ind].value=F[i];
				FF[ind].valueOccuredNumberOfTimes=1;
			}
		}
		ind+=1;

		for(int i=0;i<k;i++)
		{
			x = E[i]*(-1);
			low=0;
			high=ind;
			while((high-low)>1)
			{
				mid=(low+high)/2;
				if(FF[mid].value<x)
				low=mid;
				else
				high=mid;
			}
			if(FF[low].value==x)
			{
				cnt+=FF[low].valueOccuredNumberOfTimes;
				//cout<<FF[low].value<<" "<<FF[low].valueOccuredNumberOfTimes<<"\n";
			}
			else if(FF[high].value==x)
			{
				cnt+=FF[high].valueOccuredNumberOfTimes;
			}
		}
		cout<<cnt<<"\n";
		if(t)
		cout<<"\n";
	}

	return 0;
}