Cod sursa(job #3301069)

Utilizator abel3324Ursu Abel-Patrick abel3324 Data 21 iunie 2025 14:31:20
Problema Infasuratoare convexa Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.93 kb
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>

#define MAXN 1000007
typedef struct{
    int64_t x,y;
} point;
point punct[MAXN];
point infasuratoare[MAXN];

int N;

int cmp(const void* a,const void* b)
{
    point* p1=(point*)a;
    point* p2=(point*)b;
    if(p1->x<p2->x)return -1;
    return 1;
}
int64_t prod_vect(point O,point A,point B)
{
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}
long double calc_arie(point* inf,int size)
{
    long double arie = 0.0;
    for (int i = 0; i < size; ++i)
    {
        int j = (i + 1) % size;
        arie += (long double)inf[i].x * inf[j].y - (long double)inf[j].x * inf[i].y;
    }
    if (arie < 0) arie = -arie;
    return arie / 2.0;
}

int main(void)
{   
    FILE *fin = fopen("infasuratoare.in", "r");
    FILE *fout = fopen("infasuratoare.out", "w");
    if (fin == NULL || fout == NULL)
    {
        fprintf(stderr, "eroare la deschiderea fisierelor");
        exit(EXIT_FAILURE);
    }

    if (fscanf(fin, "%d", &N) != 1)
    {
        fprintf(stderr, "eroare la citirea numarului de puncte");
        exit(EXIT_FAILURE);
    }

    for (int i = 0; i < N; ++i)
    {
        if (fscanf(fin, "%ld %ld", &puncte[i].x, &puncte[i].y) != 2)
        {
            fprintf(stderr, "eroare la citirea punctului %d\n", i);
            exit(EXIT_FAILURE);
        }
    }
    qsort(puncte,N,sizeof(point),cmp);
    for(int i=0;i<N;i++)
    {
        while(k>=2 && prod_vect(infasuratoare[k-2],infasuratoare[k-1],infasuratoare[k])<=0)
        {
            k--;
        }
        infasuratoare[k++]=puncte[i];
    }
    k--;
    long double area = calc_area(hull, k);
    fprintf(fout, "%.4Lf\n", area);
    if (fclose(fin) != 0)
    {
        fprintf(stderr, "eroare la inchiderea fisierului de citire");
        exit(EXIT_FAILURE);
    }
    if (fclose(fout) != 0)
    {
        fprintf(stderr, "eroare la inchiderea fisierului de scriere");
        exit(EXIT_FAILURE);
    } 

    return 0;
}