Problem Statement 
 You need to write a program to race a car. The car will drive along a track, as defined by a sequence of waypoints (you don't actually have to stay on the track, you just have to hit the waypoints).
You will first be given a number of parameters relating to the performance of the car, in a method init, along with the locations of the waypoints. Your car starts out at (0,0), facing in the +x direction. A number of calls will then be made to a method step, reminding you of your current location and direction. You should return a double[] from this method, where consecutive elements of the return indicate first how much to accelerate or break, and then how much to turn the car (in radians), with the acceleration element coming first. Each turning element must have absolute value no more than 0.005, and each accelerating element must have absolute value no more than maxacc. The car's motion will be simulated in a number of discrete timesteps, corresponding to your return. Thus, a return with 6 elements, would result in the simulation running for 3 steps.
The physics of our car's motion are fairly simple (and perhaps not too realistic). The current state of the car is (mostly) defined by five values: it's x and y positions, it's x and y velocities, and the angle it is facing. It should be noted that the car may be facing in a different direction from the one it is moving in, as it might skid around a turn, or even roll backwards.
In a particular time step, you apply a forward force of up to maxacc to the car, propeling it in the direction it is facing. Air resistance works to counter that force, and the net forward force is given by the force you apply minus the forward air resistance (which is proportional to velocity squared). If the car is not moving in the same direction it is facing, there is also a cross force, which can be as large as the car's velocity in this cross direction. Finally, you can apply the breaks, slowing the car down up to maxacc in the forward direction, by returning a negative value for acceleration.
The friction of the tires can only provide a limited amount of force, which must be distributed between the cross force and the forward force. If the magnitude of the overall force vector is larger than the force of friction, then the car is said to be skidding. In this case, the force of friction is divided between the forward and cross directions. At the end of each time step, after all the forces have been computed, the car's velocity is first adjusted, and then the car's position is adjusted according to this new velocity. Finally, if the car was skidding in the previous timestep, it builds some angular momentum, and the change in it's angle will be set to whatever change you impart, plus half of the change from the previous timestep.
All this adds up to fairly intuitive motion. If you don't turn too sharply and you don't accelerate too much, the force of friction is large enough to entirely adjust the cars velocity so that it is moving in the direction it is facing, and no skidding occurs. If you turn too sharply, there isn't enough friction on the tires, and you will start to skid. In this case, the car will still turn, but it won't be moving in the direction it is facing. In extreme cases, you could turn the car all the way around, and end up rolling backwards. The amount of acceleration you can apply without exceeding the force of friction increases with your speed (so its more like power than acceleration), as air resistance is removed from forward acceleration before checking if there is enough friction.
To complete the race, you must come within 1000 units of each of the waypoints, in order. The simulation will be run for at most 100,000 steps and you will be allowed a total of 30 seconds for each test case.
Test Case Generation
The friction parameter will be uniformly chosen in [0.002,0.03]. The air resistance will be chosen in [0.0001,0.001], and the maximum acceleration will be chosen in [0.01,0.1]. The waypoints will be generated by starting at (0,0), facing in the +x direction. A sequence of moves and turns will then be made, placing a waypoint after each:
S = nextInt(91)+10;
double alpha = 0;
double cx = 0, cy = 0;
wx[0] = wy[0] = 0;
for(int i = 1; i<S; i++){
alpha += nextGaussian()/2;
double d = pow(nextDouble(),2) * 5000;
wx[i] = cx += Math.cos(alpha)*d;
wy[i] = cy += Math.sin(alpha)*d;
}
Scoring
Your raw score will be the timestep at which you hit the last of all the waypoints that you hit, plus the number of waypoints hit divided by 1000. Competitors will be ranked primarily by the number of waypoints hit (you should be able to always hit all of them), with ties broken by the speed with which you hit them. The highest rank is 1, and each competitor will get (12rank)^{2} points. Thus, the winner will get 121 points. In the event of a tie, the points for the tied places will be divided evenly. Thus, if there were a tie for first, the top two would each get (121+100)/2 points, while third would still get 81.
Resources
You can see the source code and a more detailed explanation of the physics at http://www.topcoder.com/contest/problem/CarRace/physics.html.
There is also a visualizer, described at http://www.topcoder.com/contest/problem/CarRace/vis.html. 

Definition 
 Class:  CarRace  Method:  init  Parameters:  double, double, double, double[], double[]  Returns:  int  Method signature:  int init(double friction, double air, double maxacc, double[] wx, double[] wy)    Method:  step  Parameters:  double, double, double, double, double, int  Returns:  double[]  Method signature:  double[] step(double x, double y, double dx, double dy, double alpha, int wp)  (be sure your methods are public) 




Notes 
  Breaking while going backwards still makes you stop  it doesn't accelerate you in reverse. 
  The time limit is 30 seconds and the memory limit is 512M. 
  You will have at most 100,000 steps to finish. If you don't finish all waypoints, your score will be as described in the problem, and you will be ranked behind everyone who hit more waypoints than you. 
  The direction you are facing will be between PI and PI. You will start facing in the +x direction, with alpha = 0. Turning clockwise corresponds to increasing alpha. 

Constraints 
  In each step you may turn any amount between 0.005 and 0.005. 
  In each step you may accelerate an amount between maxacc and maxacc 

Examples 
0)  
 friction = 0.025353231925443906
air = 4.965840810810231E4
maxacc = 0.010020588605228068
N = 85
 

1)  
 friction = 0.026415714551864464
air = 1.4666721060721836E4
maxacc = 0.01893924570669956
N = 92
 

2)  
 friction = 0.004844682646896966
air = 4.746660802103152E4
maxacc = 0.06236285385761371
N = 10
 

3)  
 friction = 0.02815367095844578
air = 1.8501805598421562E4
maxacc = 0.09508318371791942
N = 97
 

4)  
 friction = 0.014431617598556953
air = 7.673181465344457E4
maxacc = 0.04720944775523275
N = 26
 

5)  
 friction = 0.02400016822715227
air = 6.975636481665687E4
maxacc = 0.06782124248871851
N = 89
 

6)  
 friction = 0.0062732643115944176
air = 6.03853832499194E4
maxacc = 0.08891366051327443
N = 33
 

7)  
 friction = 0.022912046591109785
air = 9.433731971918565E4
maxacc = 0.07645501697340658
N = 18
 

8)  
 friction = 0.0025809528661937535
air = 1.0337427216509109E4
maxacc = 0.09923919367667183
N = 32
 

9)  
 friction = 0.017193956023422358
air = 1.3735350430489604E4
maxacc = 0.034056681729733335
N = 38
 

10)  
 friction = 0.012095102876343383
air = 1.350554326067197E4
maxacc = 0.09337933523810507
N = 23
 

11)  
 friction = 0.01063311914214325
air = 5.320894448422347E4
maxacc = 0.057396703337113456
N = 13
 

12)  
 friction = 0.017551334976223812
air = 5.275741890291596E4
maxacc = 0.06837013496585978
N = 35
 

13)  
 friction = 0.002780827021052145
air = 5.916970900662024E4
maxacc = 0.07667698326331136
N = 38
 

14)  
 friction = 0.02153379082007357
air = 4.2201266203282357E4
maxacc = 0.019785379399535032
N = 38
 

15)  
 friction = 0.014504300422171476
air = 1.4169402429845034E4
maxacc = 0.019126261838502728
N = 78
 

16)  
 friction = 0.018501240274952514
air = 1.5505615534243216E4
maxacc = 0.04447374141309209
N = 55
 

17)  
 friction = 0.010420957638070267
air = 1.098160773416636E4
maxacc = 0.07814826571569722
N = 56
 

18)  
 friction = 0.007461881907706251
air = 5.702494936263828E4
maxacc = 0.05444883456395739
N = 62
 

19)  
 friction = 0.006935324539288438
air = 8.158847041045977E4
maxacc = 0.08047553123971915
N = 19
 
