Hi:

I did a 4-hour programming contest this morning-early afternoon and I

had the following problem which I'll put in a nutshell, hopefully

that's enough to get even the vaguest idea as to what my code (when I

post it) was to intentionally do

--

You love playing Space Invaders. It's where ONE row of enemy bots are

on the top of the screen. You're on the bottom and may move only

horizontally. When you fire, you fire straight up till the bullet

destroys an enemy. You love the game so much that you stay all night

playing it. Therefore, you eventually get to the last and hardest

level. In this level, some of the screen is covered with polygons. If

the polygon happens to cover a particular column, firing at that

column won't do anything. So if the input tells you how wide and how

tall the screen is (I believe it was from 3 -> 10^7 for both

dimensions) and you assume that the whole top row is covered with

enemies, and in the input you're given the number of polygons and the

points of the corners of them, work out how many enemies you can

destroy on this static screen save your maneuvering of your bot.

--

What I ended up doing was creating a struct representing a polygon. It

stored the number of points needed to describe the polygon (which was

part of the input data), it had an array of all the x coordinate

values inputted for this particular polygon and stored also the

smallest and largest x value in the array. The reason I didn't store

the y coordinate is because it's not needed in my algorithm (which I

believe is correct, would have been fast enough had I managed to code

it properly...).

Once you've stored all the input into an array of ships (I declared my

type as struct ship {...} ships [10^5 + 2]

you sort the ships[] from

ship with the lowest x coordinate to the highest (ie by the ship's sx

[smallest x] increasing).

Then, essentially you sweep from the leftmost ship to the rightmost

ship. You find the difference of each ship's smallest and largest x

coordinate and subtract it from the variable, nfire (the number of

enemies you can destroy which starts off as the width inputted) and at

the end of the algorithm you output nfire.

The catch is when one ship is in front of another. Or, one ship's x

coordinate is in between another ship's smallest and largest x

coordinate. In this case, subtracting differences of smallest and

largest values from nfire wouldn't work because there will surely be

test cases where the ships 'overlap'. So - that's why I wantED to sort

my ships array. Continually searching through each ship for similar x

coordinates would timeout. A maximum of 10^5 ships can be described

and such an algorithm would take O(nships^2) which is unusable,

considering the assumption that a computer can process approximately

10^8 (but really it should be 3 * 10^8 but we like powers of ten)

instructions per second (and the time limit in most problems in this

olympiad are 1 second). So I thought the inbuilt qsort() would work

but I couldn't get it to work.

Let's simplify the problem before I get the full problem statement

again (can't access it outside the competition times anymore until

sometime) and my code which I left saved on the school network.

struct ship {

int sx;

} ships[10^5];

fscanf()....//into ships.sx

qsort(ships, 10^5, //comparison function//);

How do I get qsort to sort the array of structures accordign to sx?

Thanks

Albert