Fighting with computers

Computers are not always friendly.

Monday, August 04, 2008

Solving Triangle Areas

Vacation time is a good moment to ... keep on trying things at the computer. At least this is what I am doing now, as have been having a look at the Code Jam Round 2 problems. Again interesting problems that I have not been able to solve in two hour time. Amazingly, some guys did it with flying colors and using a bit more than one hour!

I have already done the Star Wars problem, though I would complain that there is not such a thing as "receiver power" (even on a spaceship) but "receiver sensitivity". However the problem was challenging and fun (I did a minimum search in 3D space and it worked).

I'm dealing now with the Triangle Areas problem, that though manageable in complexity it is a bit of a challenge to get right. A few ideas can help, the first one is how to know the triangle area out of set of vertices coordinates. The second observation is that if we keep one vertex at (0,0) then the area of the triangle is just 0.5*(x2*y3-x3*y2). With this idea in mind it is simpler to get the problem solved.

Update: My code loops from n,m to 0,0 for x2,y3 while the x,y value was x*y>a and then it does the opposite (from 0,0 to n,m) for the x3,y2 values till the desired area was met.

0 Comments:

Post a Comment

<< Home