Cod sursa(job #3301072)

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

#define MAXN 1000007

typedef struct {
    int64_t x, y;
} point;

point puncte[MAXN];
point infasuratoare[MAXN];

int N;
int k;

int cmp(const void* a,const void* b)
{
    point* p1=(point*)a;
    point* p2=(point*)b;
    if(p1->x!=p2->x)
    {
        if(p1->x<p2->x)return -1;
        else           return 1;
    }
    else
    {
        if(p1->y<p2->y)return -1;
        else           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);
}

double calc_arie(point* inf,int size)
{
    double arie = 0.0;
    for (int i = 0; i < size; ++i)
    {
        int j = (i + 1) % size;
        arie += (double)inf[i].x * inf[j].y - (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);

    k = 0;
    for(int i = 0; i < N; i++)
    {
        while(k >= 2 && prod_vect(infasuratoare[k-2], infasuratoare[k-1], puncte[i]) <= 0)
        {
            k--;
        }
        infasuratoare[k++] = puncte[i];
    }

    int t = k + 1;
    for(int i = N - 2; i >= 0; i--)
    {
        while(k >= t && prod_vect(infasuratoare[k-2], infasuratoare[k-1], puncte[i]) <= 0)
        {
            k--;
        }
        infasuratoare[k++] = puncte[i];
    }

    k--;

    double area = calc_arie(infasuratoare, 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;
}