Cod sursa(job #3359143)

Utilizator Sonia.06Braila Sonia Biliana Sonia.06 Data 25 iunie 2026 07:22:52
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.6 kb
#include <stdio.h>
#include <stdlib.h>

typedef struct{
    double x,y;
}punct;

int compara(const void *a, const void *b)
{
    punct *p1=(punct*)a;
    punct *p2=(punct*)b;
    if(p1->x!=p2->x)
    {
        return (p1->x>p2->x)-(p1->x<p2->x);
    }
    return (p1->y>p2->y)-(p1->y<p2->y);
}

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

int main()
{
    FILE *f,*g;
    if((f=fopen("infasuratoare.in", "r"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }
    if((g=fopen("infasuratoare.out", "w"))==NULL)
    {
        fprintf(stderr, "eroare deschidere fisier\n");
        exit(1);
    }

    int n;
    if(fscanf(f,"%d", &n)!=1)
        return 0;

    punct puncte[120001];
    for(int i=0; i<n; i++)
    {
        fscanf(f,"%lf %lf", &puncte[i].x, &puncte[i].y);
    }
    qsort(puncte, n, sizeof(punct), compara);

    int H=0;
    punct *inf=(punct*)malloc(2*n*sizeof(punct));

    for (int i=0; i<n; i++)  //partea de sus
    {
        while (H>=2 && produs(inf[H-2], inf[H-1], puncte[i])<=1e-12)
            H--;
        inf[H++]=puncte[i];
    }

    int jos=H;
    for (int i=n-2; i>=0; i--) // partea de jos
    {
        while (H>jos && produs(inf[H-2], inf[H-1], puncte[i])<=1e-12) 
        {
            H--;
        }
        inf[H++]=puncte[i];
    }

    if (n>1) H--;
    fprintf(g,"%d\n", H);
    for(int i=0; i<H; i++)
    {
        fprintf(g, "%lf %lf\n", inf[i].x, inf[i].y);
    }
    free(inf);
    fclose(f);
    fclose(g);
    return 0;
}