Algorithm to find a "balance" point

Question

I have a problem finding better complexity than O(n^2) in the following task:

"We say that point A = (a1, a2, ..., an) dominates B = (b1, b2, ..., bn ) when a1 > b1 && a2 > b2 && ... && an > bn. We are given a set of Points S and need to return an index of point which dominates and is dominated by the same amount of points (a balance point) or -1 if such a point does not exist."

int findBalancePoint(Point[] S, int n){
    int index = 0;
    int dominates, isDominated;

    for(int i = 0; i < n; i++){
        index = i;
        swap(S, 0, i);
        dominates = isDominated = 0;
        for(int j = 1; j < n; j++){
            if( S[0].x > S[j].x && S[0].y > S[j].y )
                dominates++;
            else if( S[0].x < S[j].x && S[0].y < S[j].y )
                isDominated++;
        }
        if(dominates == isDominated)
            return index;
    }

    return -1;
}

As this is an example excercise before an algorithm test I guess there is a better solution. Thanks in advance for any help.

Update

Tests:

Input1: (1,2), (2,1), (3,3), (4,4), (5,6)
Result: 2

Input2: (1,1), (3,2), (4,5)
Result: 1

Input3: (1,4), (2,3), (3,1), (4,2)
Result: 0 or 1 ( doesnt matter which one )

Input4: (1,1), (2,2), (3,3), (4,4)
Result: -1

Input5: (1,2), (2,1), (3,3), (3,5), (4,4), (5,6), (6,2)
Result: 2 or 3

Answer 1

One idea is to visit the points in order of increasing x coordinate.

As you visit each point you insert its y coordinate in a balanced binary tree (with a complexity of O(logn) per point).

You also query the binary tree to find the number of points with smaller y value, this is the number of points that it dominates.

You can then repeat this process in order of decreasing x coordinate to find the number of points that each point is dominated by.

Overall I believe this gives a O(nlogn) complexity.

Update

As Julian pointed out in the comments, this solution fails if there are multiple points with the same x coordinate. A fix for this is to do all the queries for points with the same x coordinate before adding these points to the binary tree.