We introduce a new class of solutions for Apodized Pupil Lyot Coronagraphs (APLC) with segmented aperture telescopes to remove broadband diffracted light from a star with a contrast level of $10^{10}$. These new coronagraphs provide a key advance to enabling direct imaging and spectroscopy of Earth twins with future large space missions. Building on shaped pupil (SP) apodization optimizations, our approach enables two-dimensional optimizations of the system to address any aperture features such as central obstruction, support structures or segment gaps. We illustrate the technique with a design that could reach $10^{10}$ contrast level at 34,mas for a 12,m segmented telescope over a 10% bandpass centered at a wavelength $lambda_0=$500,nm. These designs can be optimized specifically for the presence of a resolved star, and in our example, for stellar angular size up to 1.1,mas. This would allow probing the vicinity of Sun-like stars located beyond 4.4,pc, therefore fully retiring this concern. If the fraction of stars with Earth-like planets is $eta_{Earth}=0.1$, with 18% throughput, assuming a perfect, stable wavefront and considering photon noise only, 12.5 exo-Earth candidates could be detected around nearby stars with this design and a 12,m space telescope during a five-year mission with two years dedicated to exo-Earth detection (one total year of exposure time and another year of overheads). Our new hybrid APLC/SP solutions represent the first numerical solution of a coronagraph based on existing mask technologies and compatible with segmented apertures, and that can provide contrast compatible with detecting and studying Earth-like planets around nearby stars. They represent an important step forward towards enabling these science goals with future large space missions.