Triangle to Hexagon

From programming_contest
Jump to navigation Jump to search

This problem gives you a ridiculous geometrical description and asks you to compute some stuff.

First step is to calculate I and center(O). I is the intersection of the angle bisectors, and c(O) is the intersection of the perpendicular bisectors.

NOTE: always use angle. never use slope. slope breaks for vertical lines and angle doesn't.

NOTE: angle bisectors can be computed by calculating the angle that is halfway between the angles. In short, tan((arctan2(y1-y, x1-x) + arctan2(y2-y, x2-x))/2) for the slope, and then we can use the vertex coordinates as offsets

NOTE: perpendicular bisectors can be computed by adding pi/2 to the angle of the line, calculating the midpoint (just average the two points!), and then using that to find the offsets

Next we have to calculate the radius of O. This is simply the distance from center(O) to one of the triangle vertices.

Next we can calculate the intersection of the angle bisectors with O. This can either be done by finding the line perpendicular to the bisector which goes through center(O), then solving the circle intersection using trig, or we can also be lazy if we'd like and binary search along the bisector to find the point which is the right distance from center(O). Either way works.

After we've done that, we have points to define all relevant line segments, at which point, we just have to perform intersection between all the lines we need to, and calculate the distances between them.