== include(page="template/taskheader" task_id="split3") ==
Poveste şi cerinţă...
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.
h2. Date de intrare
Fişierul de intrare $split3.in$ ...
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 $x{~i~}$ şi $y{~i~}$ 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$.
h2. Date de ieşire
În fişierul de ieşire $split3.out$ ...
Î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 $a{~1~}$, $b{~1~}$, $c{~1~}$, $a{~2~}$, $b{~2~}$, $c{~2~}$ reprezentând coeficienţii ecuaţiilor celor două drepte. Ecuaţia unei drepte este $a * x + b * y + c = 0$.
h2. Restricţii
* $3 ≤ N ≤ 10^5^$
* $1 ≤ Q ≤ 10^5^$
* toate coordonatele sunt numere întregi din intervalul $[-10^6^, 10^6^]$
* se va accepta o eroare absolută sau relativă de cel mult $10^-2^$
* $3 ≤ N ≤ 50.000$
* Toate coordonatele sunt numere reale cu cel mult $9$ zecimale din intervalul $[-10^3^, 10^3^].$
* 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.
h2. Exemplu
table(example). |_. split3.in |_. split3.out |
| 4 1
1 1
3 1
3 3
1 3
2 1
| 1 0 -2 0 1 -2
| 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
|
== include(page="template/taskfooter" task_id="split3") ==
