Fişierul intrare/ieşire:infasuratoare.in, infasuratoare.outSursăad-hoc
AutorclasicaAdăugată deCatalin.FrancuCatalin Francu Catalin.Francu
Timp execuţie pe test0.3 secLimită de memorie2048 kbytes
Scorul tăuN/ADificultatenormalnormalnormalnormalnormal

Vezi solutiile trimise

Înfășurătoare convexă

Notă: Această problemă este similară cu cea de pe Infoarena, dar pune mai mult accentul pe cazuri particulare. Dacă aţi trimis deja surse pe Infoarena, puteţi să le adaptaţi pentru această problemă.

Se dă o mulţime de N puncte distincte în plan. Să se determine poligonul convex minimal care conţine în interior sau pe laturi toate punctele date. Acest poligon se numeşte înfăşurătoarea convexă a mulţimii de puncte.

Date de intrare

Fişierul de intrare infasuratoare.in conţine pe prima linie numărul de puncte N. Pe următoarele N linii se dau coordonatele xi yi ale câte unui punct, sub forma a două numere întregi despărţite printr-un spaţiu.

Date de ieşire

În fişierul de ieşire infasuratoare.out se va scrie pe prima linie numărul H de puncte de pe înfăşurătoarea convexă. Pe următoarele H linii se vor tipări vârfurile înfăşurătoarei, în ordine trigonometrică, începând cu vârful de coordonată y minimă. Dacă există două astfel de puncte, se va începe cu cel de coordonată x minimă.

Restricţii

  • 3 ≤ N ≤ 100.000
  • -1.000.000.000 ≤ xi, yi ≤ 1.000.000.000
  • H nu va depăşi 1.000
  • Înfăşurătoarea va fi mereu poligon propriu (H va fi minim 3).
  • Dacă există mai multe soluţii, se va tipări cea cu număr minim de vârfuri.

Exemplu

infasuratoare.ininfasuratoare.outExplicaţie
9
3 1
-1 1
1 -3
1 -1
-3 -1
4 -2
-2 4
-1 -2
2 -3
6
1 -3
2 -3
4 -2
3 1
-2 4
-3 -1
Trebuie sa te autentifici pentru a trimite solutii. Click aici