Exceeding time limit

Question

I'm trying to solve this problem by running this code; however, online judge says I had a timeout on only one of the tests, in which big numbers are used. How to make this code more efficient such as not to get a timeout?

#include <iostream>
using namespace std;
 
int main()
{
    int n,c=0;
    cin >> n;
    int* x = new int[n];
    int* y = new int[n];
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 0; i < n; i++) {    
        for (int counter = 1; counter + i < n; counter++) {
            int eqn1 = abs(x[i] - x[i + counter]) + abs(y[i] - y[i + counter]);
            int eqn2 = sqrt(pow(x[i] - x[i + counter], 2) + pow(y[i] - y[i + counter], 2));
            if (eqn1 == eqn2) c++;
        }
        
    }
    delete []x, y;
    printf("%d",c);
    return 0;
}

The test which I failed:

Test: #10, time: 3000 ms., memory: 1552 KB, exit code: -1, checker exit code: 0, verdict: TIME_LIMIT_EXCEEDED
Input
200000
-33112107 -488123842
-697731314 -974390012
291702602 318124465
291702602 -836483229
108627589 -985972860
-724734086 534534982
291702602 -725799533
758297688 307755976
397960964 -591981997
-888980523 802241253
-916647316 -12327823
-482711072 -476637442
108627589 -974390012
-482711072 115375745
438546882 -320123608
-482711072 318124465
437083674 115375745
437083674 -586275393
-892175582 -567584954
-162660903 -464301010
185073347 318124465
606902093 -734177138
-33112107 -48812384...

Your solution is O(n^2), too much for such a size. Hint: count the number of cases `x` are equal, number of cases `y` are equal, and number of cases both are equal. This should give a O(n logn) solution. — Damien, Mar 06 '21 at 11:29
O(.) is a classical evaluation of the complexity. Explanations here: https://stackoverflow.com/q/487258/10553341 — Damien, Mar 06 '21 at 13:26

Exceeding time limit

0 Answers0