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?