This letter combines the fast zero-moment-point approaches that work well in practice with the broader range of capabilities of a trajectory optimization formulation, by optimizing over body motion, footholds, and center of pressure simultaneously. We introduce a vertex-based representation of the support-area constraint, which can treat arbitrarily oriented point-, line-, and area-contacts uniformly. This generalization allows us to create motions, such as quadrupedal walking, trotting, bounding, pacing, combinations, and transitions between these, limping, bipedal walking, and push recovery all with the same approach. This formulation constitutes a minimal representation of the physical laws (unilateral contact forces) and kinematic restrictions (range of motion) in legged locomotion, which allows us to generate diverse motions in less than a second. We demonstrate the feasibility of the generated motions on a real quadruped robot.