Fișierul intrare/ieșire infasuratoare.in, infasuratoare.out Sursă ad-hoc
Autor clasică Adăugată de avatar Catalin.Francu Cătălin Frâncu Catalin.Francu
Timp de execuție pe test 0.3 sec Limită de memorie 2048 KB
Scorul tău N/A Dificultate stea de rating de tip fullstea de rating de tip fullstea de rating de tip emptystea de rating de tip emptystea de rating de tip empty
open book Poți vedea testele pentru această problemă accesând atașamentele .

Î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.in infasuratoare.out Explicaț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 să te autentifici pentru a trimite soluții. Click aici

Indicii de rezolvare

Arată 4 categorii