#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PRAG_EPSILON 1e-12
#define LIMITA_MAXIMA 120005
long double vector_puncte[LIMITA_MAXIMA][2];
long double stiva_poligon[LIMITA_MAXIMA][2];
long double coord_baza_x, coord_baza_y;
long double produs_vectorial(long double x_a, long double y_a, long double x_b, long double y_b, long double x_c, long double y_c)
{
return (x_b - x_a) * (y_c - y_a) - (y_b - y_a) * (x_c - x_a);
}
long double calcul_distanta(long double orig_x, long double orig_y, long double dest_x, long double dest_y)
{
return (orig_x - dest_x) * (orig_x - dest_x) + (orig_y - dest_y) * (orig_y - dest_y);
}
int comparator_unghiular(const void *element_a, const void *element_b)
{
long double *punct_1 = (long double*)element_a;
long double *punct_2 = (long double*)element_b;
long double rezultat_orientare = produs_vectorial(coord_baza_x, coord_baza_y, punct_1[0], punct_1[1], punct_2[0], punct_2[1]);
if(rezultat_orientare < -PRAG_EPSILON)
return -1;
if(rezultat_orientare > PRAG_EPSILON)
return 1;
long double dist_1 = calcul_distanta(coord_baza_x, coord_baza_y, punct_1[0], punct_1[1]);
long double dist_2 = calcul_distanta(coord_baza_x, coord_baza_y, punct_2[0], punct_2[1]);
if(dist_1 < dist_2)
return -1;
if(dist_1 > dist_2)
return 1;
return 0;
}
int main() {
FILE *fisier_intrare, *fisier_iesire;
fisier_intrare = fopen("infasuratoare.in", "r");
if(!fisier_intrare)
{
fprintf(stderr, "Eroare la deschiderea fisierului de intrare");
return -1;
}
fisier_iesire = fopen("infasuratoare.out", "w");
if(!fisier_iesire)
{
fprintf(stderr, "Eroare la deschiderea fisierului de iesire");
fclose(fisier_intrare);
return -1;
}
int numar_total_puncte;
fscanf(fisier_intrare, "%d", &numar_total_puncte);
int indice_minim = 1;
for(int contor = 1; contor <= numar_total_puncte; contor++)
{
fscanf(fisier_intrare, "%Lf %Lf", &vector_puncte[contor][0], &vector_puncte[contor][1]);
if(vector_puncte[contor][0] < vector_puncte[indice_minim][0])
indice_minim = contor;
else if(vector_puncte[contor][0] == vector_puncte[indice_minim][0] && vector_puncte[contor][1] < vector_puncte[indice_minim][1])
indice_minim = contor;
}
long double valoare_temporara;
valoare_temporara = vector_puncte[1][0];
vector_puncte[1][0] = vector_puncte[indice_minim][0];
vector_puncte[indice_minim][0] = valoare_temporara;
valoare_temporara = vector_puncte[1][1];
vector_puncte[1][1] = vector_puncte[indice_minim][1];
vector_puncte[indice_minim][1] = valoare_temporara;
coord_baza_x = vector_puncte[1][0];
coord_baza_y = vector_puncte[1][1];
qsort(vector_puncte + 2, numar_total_puncte - 1, sizeof(vector_puncte[0]), comparator_unghiular);
stiva_poligon[1][0] = vector_puncte[1][0];
stiva_poligon[1][1] = vector_puncte[1][1];
stiva_poligon[2][0] = vector_puncte[2][0];
stiva_poligon[2][1] = vector_puncte[2][1];
int dimensiune_stiva = 2;
for(int contor = 3; contor <= numar_total_puncte; contor++)
{
while(dimensiune_stiva >= 2 && produs_vectorial(stiva_poligon[dimensiune_stiva - 1][0], stiva_poligon[dimensiune_stiva - 1][1], stiva_poligon[dimensiune_stiva][0], stiva_poligon[dimensiune_stiva][1], vector_puncte[contor][0], vector_puncte[contor][1]) > PRAG_EPSILON)
dimensiune_stiva--;
dimensiune_stiva++;
stiva_poligon[dimensiune_stiva][0] = vector_puncte[contor][0];
stiva_poligon[dimensiune_stiva][1] = vector_puncte[contor][1];
}
fprintf(fisier_iesire, "%d\n", dimensiune_stiva);
for(int contor = dimensiune_stiva; contor >= 1; contor--)
fprintf(fisier_iesire, "%.9Lf %.9Lf\n", stiva_poligon[contor][0], stiva_poligon[contor][1]);
fclose(fisier_intrare);
fclose(fisier_iesire);
return 0;
}