Return to Revisions

Algorithmic optimizations.

As you read the values in work out what quadrant the point belongs to and keep a running total for each quadrant (not adjustment needed on X/Y query). Then you do not need to re-calculate everything every time there is a 'C' request.

As it stands complexity for each C request of O(n). If you keep a running total then it is merely o(1). Think of the situation where you have a 1,000,000 points and you do a 1,000,000 C requests. The code would basically do 1,000,000 * 1,000,000 operations rather than just 1,000,000.

Style

Please stop using this:

using namespace std;

For simple ten line programs it makes things simpler. But once you get past that stage it makes things exceedingly more complex. By causing name clashing problems. It is preferable to prefix stuff in the standard namespace with std:: (why do you think they kept it so short).

A personal opinion. So feel free to ignore. But to distinguish types and objects. I nae types with a leading capitol letter. A lower case indicates an object (or reference).

typedef pair <int,int> pii;

What happens below if any point is on the line (first or second == 0)?

 if ( (pointList[k].first > 0 ) && ( pointList[k].second > 0) ) {
 q1++;
 }
 else if ( (pointList[k].first < 0) && ( pointList[k].second > 0) ) {
 q2++;
 }
 else if ( ( pointList[k].first < 0) && (pointList[k].second < 0 ) ) {
 q3++;
 }
 else if ( ( pointList[k].first > 0) && (pointList[k].second < 0 ) ) {
 q4++;
 }
}

Here:

void performXYquery(char qType, int i, int j, vector< pii > &pointList)

For readability I would just make this two separate functions performXquery() and performYquery(). It make the code more readable and removes the need for an if statement in the middle of a tight loop.

There is a standard utility function for creating std::pair<> called make_pair.

 pii temp(x,y);
 pointList.push_back(temp);
 // can be written as:
 pointList.push_back(std::make_pair(x, y));

Since qName is a char you can use a switch statement here:

 if (qName == 'C') {
 performCquery(startIndex,endIndex, pointList);
 }
 else if (qName == 'X' || qName == 'Y') {
 performXYquery(qName, startIndex,endIndex, pointList);
 }
 // can be written as:
 switch(qName)
 {
 case 'C': performCquery(startIndex,endIndex, pointList);break;
 case 'X': performXquery(startIndex,endIndex, pointList);break;
 case 'Y': performYquery(startIndex,endIndex, pointList);break;
 default: /* Error Msg */
 }

No need to return 0 from main() in C++. If no explicit return is placed then an automatic return 0 is planted.

Algorithmic optimizations.

As you read the values in work out what quadrant the point belongs to and keep a running total for each quadrant (not adjustment needed on X/Y query). Then you do not need to re-calculate everything every time there is a 'C' request.

As it stands complexity for each C request of O(n). If you keep a running total then it is merely o(1). Think of the situation where you have a 1,000,000 points and you do a 1,000,000 C requests. The code would basically do 1,000,000 * 1,000,000 operations rather than just 1,000,000.

Macro optimizations

Only do these to make the code more readable. Usually the compiler already handles this kind of optimization. Assume we have an average distribution of points in 4 quadrants:

100 pts // cmp == conditional test like > or < 
25 in q1 use 2 cmp // must pass both to enter
25 in q2 use 3.5 cmp // Note: average (12.5 will do 3 cmp 12.5 will do 4 cmp)
25 in q3 use 5 cmp // to enter the code section that will do q2++
25 in q4 use 6.5 cmp
Total: 425 cmp

If we change the code so you include values on the line (ie first or second == 0) in an appropriate quadrant. You don't need the last if statement which reduces the number of comparisons so that:

100 pts // cmp == conditional test like > or < 
25 in q1 use 2 cmp // must pass both to enter
25 in q2 use 3.5 cmp 
25 in q3 use 5 cmp
25 in q4 use 4.5 cmp
Total: 375 cmp

If we re-range the tests:

if (first >= 0)
{
 if (second >= 0) ++q1;
 else ++q4;
}
else // first = 0
{
 if (second >= 0) ++q2;
 else ++q3;
}

In this case there are always 2 cmp:

100 nodes * 2 cmp = 200 cmp
Approximately a 100% reduction in the number of cmp.
Note: this does not mean a doubling of speed (maybe a slight improvement on average).
 Assuming the compiler has not already worked this out.

But in my opinion makes the code more readable.