Faits: Faits: A. Sieur A._ est propriétaire de la parcelle no yyy de la commune de Cologny. Après avoir, dans un premier temps, chargé un tiers architecte de la réalisation d'une piscine sur la propriété susmentionnée, les époux A._ (ci-après: les époux) ont renoncé à ce mandat avant de confier les travaux à X._ SA, qui offre ses services dans le métier du bâtiment, le génie civile et la démolition. Le 18 juin 1997, les parties ont signé les conditions générales du contrat d'entreprise et le 25 juin 1997, les époux ont signé un devis mentionnant un prix forfaitaire, clés en mains, de 347'190 fr. Les travaux ont commencé à la fin du mois de juin 1997 et la mise en eau de la piscine a eu lieu le 14 août 1997. Courant mars et avril 1998, X._ SA a exécuté toute une série de travaux de réfections, corrections et compléments (étanchéité de la dalle en encorbellement et de la rigole, dépose des margelles et agrandissement de la rigole, reprise des travaux d'étanchéité). Le 12 mai 1998, X._ SA a fait parvenir aux époux une facture finale d'un montant total de 362'588 fr. 85 comprenant quelques travaux supplémentaires commandés en cours d'exécution, dont la différence avec le devis du 25 juin 1997 n'a jamais été contestée par les époux. A cette date, ceux-ci restaient devoir à X._ SA la somme de 157'388 fr. 85, soit 100 (recte: 59'100) fr. (solde de situation no 2 au 31 juillet 1997), 40'600 fr. (situation no 3 au 31 août 1998 - recte: 1997) et 57'688 fr. 85 (situation no 4 au 30 avril 1998). Le 15 juin 1998, B._, ingénieur conseil déjà mandaté unilatéralement par les époux à la fin de mois d'août 1997, a établi un nouveau rapport dont il a été retenu que la piscine fonctionnait correctement, que les fissures sur le front extérieur de l'encorbellement étaient superficielles et pouvaient être masquées esthétiquement avec un enduis approprié, enfin que les travaux restés en souffrance selon liste établie par le maître étaient achevés. Le 12 avril 1999, X._ SA a fait notifier aux époux des commandements de payer les sommes de 59'100 fr. avec intérêt à 7,25 % l'an dès le 30 septembre 1997, 40'600 fr. avec intérêt à 7,25 % l'an dès le 30 octobre 1997 et 57'688 fr. 85 avec intérêt à 7,25 % l'an dès le 12 juillet 1998. Les époux y ont fait opposition. Le 12 avril 1999, X._ SA a fait notifier aux époux des commandements de payer les sommes de 59'100 fr. avec intérêt à 7,25 % l'an dès le 30 septembre 1997, 40'600 fr. avec intérêt à 7,25 % l'an dès le 30 octobre 1997 et 57'688 fr. 85 avec intérêt à 7,25 % l'an dès le 12 juillet 1998. Les époux y ont fait opposition. B. Le 30 avril 1999, X._ SA a saisi le Tribunal de première instance du canton de Genève d'une action en paiement et en mainlevée. Par jugement du 6 mars 2003, cette autorité a condamné les époux à verser à X._ SA les sommes de 59'100 fr. plus intérêt à 7,25 % l'an dès le 30 septembre 1997, 40'600 fr. plus intérêt à 7,25 % l'an dès le 30 octobre 1997 et 57'688 fr. 85 plus intérêt à 7,25 % l'an dès le 12 juillet 1998, le tout sous déduction de 20'000 fr. - montant admis par X._ SA -, ainsi qu'à des dépens. En cours d'instance, une expertise judiciaire a été mise en oeuvre, dont il ressort en substance ce qui suit. Le prix demandé est normal pour un ouvrage que l'on peut qualifier de haut de gamme. L'étanchéité de la plage en encorbellement est vraisemblablement fissurée, mais les règles de l'art n'envisagent pas la pose d'une étanchéité de ce type ou à fortiori de type lourd (toiture). L'ouvrage est acceptable sous réserve des travaux de réfection décrits (20'000 fr.). La moins-value équivaut à ce chiffre. Les travaux proposés par les époux (dépôt du granit afin d'installer une étanchéité lourde, enlèvement du béton, mise en place de l'étanchéité, repose du béton et du granit) sont disproportionnés. Répondant précisément à la question numéro neuf libellée "quels sont les travaux nécessaires pour rendre l'ouvrage conforme aux règles de l'art et conforme à ce que les maîtres de l'ouvrage pouvaient raisonnablement en attendre relativement à l'environnement, au cadre et au coût de l'ouvrage", l'expert a décrit les travaux à entreprendre et les a chiffrés à 18'000 fr., montant auquel s'ajoute la réfection du fronton circulaire de la plage, pour un coût de 2'000 fr. Entendu le 4 décembre 2002, l'expert a confirmé son rapport et considéré qu'aucune nouvelle intervention lourde n'était nécessaire, que des travaux de démolition et de reconstruction seraient disproportionnés et qu'ils ne se justifiaient pas au regard de quelques gouttes d'eau qui pourraient suinter. Statuant sur appel des époux du 5 mai 1993 (recte: 2003), la Cour de justice du canton de Genève a, par arrêt du 13 février 2004, confirmé le jugement rendu par le Tribunal de première instance et condamné ceux-ci aux dépens d'appel. Statuant sur appel des époux du 5 mai 1993 (recte: 2003), la Cour de justice du canton de Genève a, par arrêt du 13 février 2004, confirmé le jugement rendu par le Tribunal de première instance et condamné ceux-ci aux dépens d'appel. C. Les époux A._ (les recourants) interjettent un recours de droit public au Tribunal fédéral. Invoquant la violation de leur droit d'être entendus et l'arbitraire, ils concluent à l'annulation de l'arrêt entrepris, avec suite de frais et dépens. X._ SA (l'intimée) conclut au rejet du recours, avec suite de frais et dépens. Pour sa part, la Cour de justice se réfère aux considérants de son arrêt. Parallèlement à leur recours de droit public, les époux A._ ont également interjeté un recours en réforme au Tribunal fédéral.