Spoj SUMFOUR

Problem Link: [http://www.spoj.com/problems/SUMFOUR/]
Category: Binary Search
Strategy: At the first sight of this problem, it seems to use four nested loop (O(n^4), bruteforce) here. We can optimise it like this:
          if   A + B + C + D=0
         then, A+B= -(C+D)

At this sense, first we can generate LHS and RHS values and store them in separate array with O(n^2) nested loop . Then we can use binary search technique to count the equality of LHS and RHS values.

Reading Material:(In Quora)
     [https://www.google.com.bd/url?sa=t&rct=j&q=&esrc=s&source=web&cd=4&cad=rja&uact=8&ved=0ahUKEwjvmoKa3_3OAhWItY8KHX-PDmsQFgguMAM&url=https%3A%2F%2Fwww.quora.com%2FHow-do-I-solve-the-SUMFOUR-problem-of-SPOJ&usg=AFQjCNFJI2ZOLQ0c-gD7oG45OYIgh7bj9g&sig2=drrv9Y10g22Gaeaw_rk3FA]


Code:

#include<bits/stdc++.h>
	#define ll int
	using namespace std;
	int main()
	{
	/*ifstream infile;
	infile.open("A-large.in");
	//freopen("output_file_name.out","w",stdout);
	ofstream outfile;
	outfile.open("output_file_name.out");*/
	ll n,a[4005],b[4005],c[4005],d[4005];
	vector <ll>f,s;
	cin>>n;
	for(ll i=0; i<n; i++)
	cin>>a[i]>>b[i]>>c[i]>>d[i];
	for(ll i=0; i<n; i++)
	{
	for(ll j=0; j<n; j++)
	{
	f.push_back(a[i]+b[j]);
	s.push_back(c[i]+d[j]);
	}
	}
	ll co=0;
	ll f1=1, f2=1,i=0,j=s.size()-1;
	sort(f.begin(),f.end());
	sort(s.begin(),s.end());
	while(i<f.size() && j>=0)
	{
	while(f[i+1]==f[i] && i+1<f.size())i++, f1++;
	while(s[j-1]==s[j] && j-1>=0)j--, f2++;
	if(f[i]==-s[j])co+=f1*f2,f1=1,f2=1,i++,j--;
	else if(-s[j]<f[i])j--,f2=1;
	else if(-s[j]>f[i]) i++,f1=1;
	}
	cout<<co<<endl;
	}