Fişierul intrare/ieşire:split3.in, split3.outSursăAlgoritmiada 2014, Runda Finala
AutorAdrian Budau, Andrei Heidelbacher, Eugenie Daniel PosdarascuAdăugată dea_h1926Heidelbacher Andrei a_h1926
Timp execuţie pe test0.25 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

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.insplit3.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
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content