Fișierul intrare/ieșire | infasuratoare.in, infasuratoare.out | Sursă | ad-hoc |
---|---|---|---|
Autor | clasică | Adăugată de | 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 |
Vezi soluțiile trimise | Statistici
Î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 |
|