Overcoming an n^2 runtime program

Question

Is there a way to overcome a nested loop recursion in C++11? My program has a slow runtime. Or rather, is there a more efficient way to solve for the following formula z=|a-b|*|x-y|,with a, b, x and y being elements in a 10000 integer array?

Here is the code:

#include <iostream>
#include <fstream>
#include <cmath>
using namespace std;

ifstream in("int.in");

int main()
{
    long long n, n1, z, x, y, in2=0;
    in>>n
    long long l[n], p[n];
    for(x=0;x!=n;x++)
        in>>l[x]>>p[x];
    for(x=0;x!=n;x++)
    {
        for(y=x+1;y<n;y++)
        {
            ineq+=(abs(l[x]-l[y])*abs(p[x]-p[y]))); //executes slow
            /*n1=l[x]-l[y]; //Alternative algorithm
            if(n1<0)
                n1*=-1;
            z=p[x]-p[y];
            if(z<0)
                z*=-1;
            in2+=n1*z;*/
        }
    }
    cout<<in2<<"\n";
}

I tried to change the data types to short int, long, long long and unsigned, but it either dumps garbage values or executes ``Segmentation Core Fault` errors.

For the absolute value formula, I originally tried using a hard-coded approach (commented out), but it seemingly outputs garbage values. I've also tried to optimize the abs solution with the abs() function ineq+=abs(l[x]-l[y])*abs(p[x]-p[y]));, but it seems to execute slower. I do not know of any other optimizations I can implement, so please do recommend some.

Linux-friendly solution preferred. Thank you.

Side Note: the values of a, b, x and y are all within the range 1<=a,b,x,y<=10000.

Side Note: this program reads from a file "int.in", takes the first integer (the number of items) and reads each new line by pair (l[x] and p[x] are pairs).

Side Note: I also tried using only a multidimensional array, but I read somewhere that a one dimension array is in the CPU cache, while multidimensions are scattered in the memory and is slower.

Answer 1

The problem can be drawn in another way: you're looking for c and d (both positive) in the equation z=c*d (of course c is |a-b| and d is |x-y|).

So first order your arrays. Then look for solution of z=c*d then find which a and b make c == a - b true and x and y that make d == x - y true.

Once it's done you've got all the values that makes your equation true since abs(a-b) is the same as abs(b-a)