Fişierul intrare/ieşire:poligon2.in, poligon2.outSursă.campion 2003
AutorMugurel Ionut AndreicaAdăugată de
Timp execuţie pe test0.1 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise | Statistici

Poligon 2

Gigel a desenat pe hartie un poligon (nu neaparat convex si care se poate chiar autointersecta) cu N varfuri si a marcat mijlocul fiecarei laturi. Fratele lui, insa, a sters poligonul desenat, pe hartie ramanand marcate numai mijloacele laturilor. Gigel ar dori, totusi, sa redeseneze poligonul, asa cum era el initial. Se considera ca poligonul are varfurile numerotate de la 1 la N, in ordinea in care apar pe conturul poligonului. Cu aceasta numerotare a varfurilor, se defineste si o numerotare a laturilor. Latura i (1 ≤ i ≤ N) este segmentul ce uneste varfurile i si i + 1. Latura N uneste varfurile 1 si N.

Cerinta

Dandu-se coordonatele mijloacelor laturilor unui poligon, determinati coordonatele varfurilor sale.

Date de intrare

Pe prima linie a fisierului de intrare poligon2.in se afla numarul intreg N, de laturi (si varfuri) ale poligonului. Pe urmatoarele N linii se afla cate doua numere reale (cu maxim trei zecimale), separate printr-un spatiu, x si y, reprezentand coordonatele mijloacelor fiecarei laturi, in ordine, de la 1 la N.

Date de iesire

Fisierul de iesire poligon2.out va contine mesajul fara solutie, in cazul in care Gigel a marcat gresit mijloacele laturilor si nu se poate forma nici un poligon avand mijloacele laturilor date. In cazul in care exista cel putin o solutie, veti afisa N linii. Fiecare linie va contine doua numere reale, afisate cu trei zecimale, reprezentand coordonatele (x,y) ale unui varf. Pe prima linie se vor afisa coordonatele varfului numerotat cu 1, pe a doua linie, coordonatele varfului numerotat cu 2 s.a.m.d.

Restrictii

  • 3 ≤ N ≤ 10.000
  • Coordonatele mijloacelor laturilor sunt din intervalul [0, 2.000.000.000].
  • In cazul in care problema admite cel putin o solutie, cu coordonatele varfurilor afisate in fisierul de iesire, se va calcula, pentru fiecare latura, coordonatele mijlocului acesteia. Veti primi punctaj maxim pentru testul respectiv, daca diferenta dintre valoarile calculate ale coordonatelor mijlocului si cele date in fisierul de intrare este cel mult 0,001, pentru oricare latura. Altfel, nu veti primi nici un punct.

Exemple

poligon2.inpoligon2.out
4
0 0
2 0
2 2
0 2
-1.000 1.000
1.000 -1.000
3.000 1.000
1.000 3.000
4
0 0
2 0
2 2
1 3
fara solutie
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content