0

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?

2
Contributors
4
Replies
6
Views
7 Years
Discussion Span
Last Post by am5a03
0

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

0

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:

0

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 by am5a03: n/a

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.