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?

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

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

Thanks for answering!

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:

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.

Thanks for your kindly help!

Edited 6 Years Ago by am5a03: n/a

This article has been dead for over six months. Start a new discussion instead.