#include <stdio.h>
#include <stdlib.h>
#include <math.h>

typedef struct {
    double x;
    double y;
} Punct;

double produsVectorial(Punct A, Punct B, Punct C) {
    return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}

double distanta(Punct A, Punct B) {
    return sqrt((B.x - A.x) * (B.x - A.x) + (B.y - A.y) * (B.y - A.y));
}

int compara(const void* a, const void* b) {
    Punct A = *((Punct*)a);
    Punct B = *((Punct*)b);
    double unghiA = atan2(A.y, A.x);
    double unghiB = atan2(B.y, B.x);
    if (unghiA < unghiB) return -1;
    if (unghiA > unghiB) return 1;
    return 0;
}

void acoperireConvexa(Punct P[], int n) {
    if (n < 3) return;

    int minIdx = 0;
    for (int i = 1; i < n; i++) {
        if (P[i].y < P[minIdx].y || (P[i].y == P[minIdx].y && P[i].x < P[minIdx].x)) {
            minIdx = i;
        }
    }

    Punct temp = P[0];
    P[0] = P[minIdx];
    P[minIdx] = temp;

    qsort(&P[1], n - 1, sizeof(Punct), compara);

    Punct* stiva = (Punct*)malloc(n * sizeof(Punct));
    int top = 2;
    stiva[0] = P[0];
    stiva[1] = P[1];
    stiva[2] = P[2];

    for (int i = 3; i < n; i++) {
        while (produsVectorial(stiva[top - 1], stiva[top], P[i]) <= 0) {
            top--;
        }
        top++;
        stiva[top] = P[i];
    }

    printf("Punctele acoperirii convexe (în sens trigonometric):\n");
    for (int i = 0; i <= top; i++) {
        printf("(%.2f, %.2f)\n", stiva[i].x, stiva[i].y);
    }

    free(stiva);
}

int main() {
    Punct P[] = {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    int n = sizeof(P) / sizeof(P[0]);
    acoperireConvexa(P, n);
    return 0;
}