Judging the Southeast Region

This one was just Math. Some teams solved this very quickly, others struggled with it. It was still one of the 4 most solved problems. There were several ways to approach it, which you’ll see in the spoiler.

Check out the Judge Input, the Judge Output, the main Solving Program, another solution, and another, and another, and one in C++.

[spoiler]
I’ll talk about three different solutions, but all of them have one thing in common. They all express points G and H, (and, more specifically, their coordinates Gx, Gy, Hx and Hy) parametrically in terms of a parameter t. This parameter represents how far along ray AC point H is. If t=0, then H is right at A. If t=1, then H is right at C. If 0<t<1, H is between A and C. If t>1, then H is further away from A than C is. Once we know t, we can figure out all the coordinates like this:

Hx = Ax + t*(Cx-Ax)
Hy = Ay + t*(Cy-Ay)
Gx = Bx + t*(Cx-Ax)
Gy = By + t*(Cy-Ay)

The first solution, in euclid.java, is a closed-form solution using more trig than anything else. It uses Heron’s formula to get the area of triangle DEF. It then uses the Law of Cosines to get the cosine of angle CAB. Using the distance of line segment AB (we’ll notate that |AB|), and our target area, we can compute the height of the desired parallelogram as area/|AB|. Since we know the cosine of CAB, we can easily compute the sine, and then use the Law of Sines to get the distance we need along ray AC. Then, t = distance / |AC|. The rest is as above.

The second solution, in euclid_binary.java, uses an age-old trick to get the area of any polygon. For every edge (x1,y1) to (x2,y2), add up (y2+y1)*(x2-x1). The area of the polygon is one half of the absolute value of that. Or,

area = 0.5*|∑(y2+y1)*(x2-x1)|

It uses that trick to get the area of triangle DEF. It then uses that trick to get the area of a parallelogram given parameter t, and uses Binary Search to nail down the correct value of t.

The third solution, in euclid_chinmay.java, uses the fact that the magnitude of the cross product of two vectors (with the same base) gives the area of the paralellogram defined by those two vectors. Also, half of that would be the area of the triangle defined by those two vectors. So, the area of triangle DEF is 0.5*|DExDF|. The area of a parallelogram defined by CAB is |ACxAB|. Then, just let t = 0.5*|DExDF| / |ACxAB|, and we have our answer. This works because the area of the parallelogram we seek will be linearly related to the distance that H is from A along AC.

The other solutions, euclidYiu.java and euclid.cpp, use various combinations of these techniques.
[/spoiler]