## am5a03

Hello, guys!
I got a problem here:

You're given set of x-y coordinates (at lease 2 and at most 60000). You need to find out the number of positive slopes formed by those coordinates.

e.g.
4(this is the number of points that you want to pass)
0 0
1 1
2 2
3 3
I got 6 pairs of +ve slopes.

I observed that whenever x1>x2 and y1>y2, 1 pair of +ve slope is formed and I just come up with this stupid brute-force method.

``````for (int i = 0; i<pos.size(); ++i)
for(int j = 0; j<pos.size(); ++j){
if ((pos[i].x > pos[j].x)&&(pos[i].y > pos[j].y))
++pairup;
}``````

It works but it took me 5 secs to complete but the requirement is 1 sec.

I've tried to use this sorting function:
sort(pos.begin(), pos.end(), SortByXY)

``````//coor is struct, containing integer x and integer y
bool SortByXY(const coor& pass1, const coor& pass2){
if ((pass1.x < pass2.x)&&(pass1.y < pass2.y)){
++pairup;
return true;
}
else
return false;
}``````

However, it doesn't work here:'(
Can anyone give me any suggestion?

## firstPerson 761

your idea is fine. Just don't use stl containers. use regular arrays if you wan't speed since this is all about speed.

## am5a03

your idea is fine. Just don't use stl containers. use regular arrays if you wan't speed since this is all about speed.

I've tried to change it form vector to dynamic array. Remove the sorting part and just use brute-force.
However, it still doesn't meet the requirement.:icon_sad:

## firstPerson 761

show the whole program

## am5a03

show the whole program

``````#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct coor{
int x, y;
};

bool SortByX(const coor& pass1, const coor& pass2){
return(pass1.x < pass2.x);
};

int main(){
int size;
coor input;
vector<coor> pos;

cin >> size;
for (int i = 0; i<size; ++i){
cin >> input.x >> input.y;
pos.push_back(input);
}
sort(pos.begin(), pos.end(),SortByX);
int pairup = 0;
for (int i = 0; i<pos.size(); ++i)
for(int j = i; j<pos.size(); ++j){
if (pos[i].y < pos[j].y)
++pairup;
}

cout << pairup;

}``````

This is a newer version of the coding, I just sort the coordinate by X only.

In fact, I've found some hint in my Discrete maths book - "The closet-pair problem". The divide and conquerer algorithm may seem to solve my problem here. However, I don't know how to divide them yet.