Fişierul intrare/ieşire: | split3.in, split3.out | Sursă | Algoritmiada 2014, Runda Finala |
Autor | Adrian Budau, Andrei Heidelbacher, Eugenie Daniel Posdarascu | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 65536 kbytes |
Scorul tău | N/A | Dificultate |
Vezi solutiile trimise | Statistici
Split3
Tassadar se juca “Slice It!” pe telefon şi i-a venit ideea să compună o problemă pentru Algoritmiada. Dacă reuşiţi să rezolvaţi problema, vă recompensează cu 100 de puncte.
Se dă un poligon convex cu N vârfuri şi un punct Q aflat pe marginea sa. Se cere să găsiţi două drepte care să îndeplinească următoarele proprietăţi:
1. Prima dreaptă trece prin punctul Q.
2. Cele două drepte împart poligonul în patru regiuni cu arii egale.
Date de intrare
Fişierul de intrare split3.in conţine pe prima linie numărul natural N cu semnificaţia din enunţ. Pe următoarele N linii se vor afla câte două numere reale xi şi yi reprezentând coordonatele vârfurilor poligonului, în ordine trigonometrică. Pe linia următoare se vor afla două numere reale x şi y reprezentând coordonatele punctului Q.
Date de ieşire
În fişierul de ieşire split3.out veţi afişa pe o singură linie, separate prin câte un spaţiu, numerele reale a1, b1, c1, a2, b2, c2 reprezentând coeficienţii ecuaţiilor celor două drepte. Ecuaţia unei drepte este a * x + b * y + c = 0.
Restricţii
- 3 ≤ N ≤ 50.000
- Toate coordonatele sunt numere reale cu cel mult 9 zecimale din intervalul [-103, 103].
- Se va accepta o eroare de cel mult 10-2, mai exact diferenta dintre aria cea mai mare dintre cele 4 poligoane si area cea mai mica dintre cele 4 poligoane sa fie cel mult 10-2
- Se recomandă să afişaţi numerele din fişierul de ieşire cu 9 zecimale.
- Se recomandă să folosiţi o precizie de cel puţin 10-6 atunci când comparaţi numere reale.
- Pentru 30% din teste, poligonul va fi regulat.
Exemplu
split3.in | split3.out |
---|---|
4 1.0 1.0 3.0 1.0 3.0 3.0 1.0 3.0 2.0 1.0 | -1.0 0.0 2.0 0.0 1.0 -2.0 |