Cod sursa(job #3301142)

Utilizator Magulean_Mihai-VictorMagulean Mihai-Victor Magulean_Mihai-Victor Data 21 iunie 2025 21:24:51
Problema Infasuratoare convexa Scor 80
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.52 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct
{
    double x,y;
} punct;

punct puncte[120002];

double min_x, min_y;
int min_i;

double cross(punct p1, punct p2, punct p3) {
    return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
}

int compar(const void* a, const void* b) {
    punct* p1 = (punct*)a;
    punct* p2 = (punct*)b;
    return cross(puncte[1], *p1, *p2) >= 0;
}


int main()
{
    FILE* fin, *fout;
    fin = fopen("infasuratoare.in", "r");
    fout = fopen("infasuratoare.out", "w");
    int n,i;
    fscanf(fin,"%d", &n);
    fscanf(fin, "%ll %lf", &puncte[1].x, &puncte[1].y);
    min_x = puncte[1].x, min_y = puncte[1].y, min_i = 1;
    for(i=2;i<=n; i++){
        fscanf(fin, "%lf %lf", &puncte[i].x, &puncte[i].y);
        if(puncte[i].x<min_x || puncte[i].x==min_x && puncte[i].y<min_y)
        {
            min_i = i;
            min_x = puncte[i].x;
            min_y = puncte[i].y;
        }
    }
    punct aux;
    aux = puncte[1];
    puncte[1] = puncte[min_i];
    puncte[min_i] = aux;
    qsort(puncte+2, n-1, sizeof(punct), compar);


    punct stv[120002];
    stv[1] = puncte[1];
    stv[2] = puncte[2];
    int cap = 2;
    for(i=3; i<=n; i++)
    {
        while(cross(stv[cap-1], stv[cap], puncte[i]) > 0 && cap>=2) cap--;
        stv[++cap] = puncte[i];
    }
    fprintf(fout, "%d\n", cap);
    for(i=cap; i>=1; i--)
        fprintf(fout, "%lf %lf\n", stv[i].x, stv[i].y);
    fclose(fin);
    fclose(fout);
    return 0;
}