Solving Collisions in a car game

Okay, currently I have been making a car game and have started implementing powerups, the main problem is the fact that I just realised the way of detecting collisions is so inefficient that it is sickening.

Currently I am checking each powerup against each vehicle, and each vehicle against all others.

v(v-1)/2 + pv

(Where v is the amount of vehicles and p is the amount of powerups)

This is before I use the algorithms to check if they are even colliding (I cheated and used circles, 75% efficiencey... need better) (Checking the Hypotenuse of a triangle based on Pythragorus to the radius of the 2 objects).

This is before I have even implemented any tracks which will have walls and environmental obsticles.

Is there a much more efficient way (based on runtime) to check around the vehicles to see what it is colliding with? Should I set up a game grid and check the 9 squares around the vehicle?

Also anyone have any good ideas/examples of Square Colliisons in java?