Cod sursa(job #3359027)

Utilizator Alexia_vAlexia Verebeli Alexia_v Data 22 iunie 2026 23:40:27
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include<stdio.h>
#include<stdlib.h>

#define EPS 1e-12
#define MAX 120000

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

int comparare(const void *a,const void *b)
{
    const Point *p1=(const Point *)a;
    const Point *p2=(const Point *)b;

    if(p1->x < p2->x)
        return -1;
    if(p1->x > p2->x)
        return 1;

    if(p1->y < p2->y)
        return -1;
    if(p1->y > p2->y)
        return 1;

    return 0;
}

double cross(Point a,Point b,Point c)
{
    return (b.x - a.x) * (c.y-a.y) - (b.y-a.y) * (c.x-a.x);
}

int main()
{
    FILE *f=fopen("infasuratoare.in","r");
    FILE *g=fopen("infasuratoare.out","w");

    if(f==NULL || g==NULL)
    {
        perror("eroare deschidere fisier");
        return 1;
    }

    int n;
    static Point puncte[MAX];
    static Point stiva[2*MAX+5];

    if(fscanf(f,"%d",&n)!=1)
    {
        printf("citire incorecta\n");
        return 1;
    }

    for(int i=0;i<n;i++)
    {
        if(fscanf(f,"%lf %lf",&puncte[i].x,&puncte[i].y)!=2)
        {
            printf("citire incorecta\n");
            return 1;
        }
    }

    qsort(puncte,n,sizeof(Point),comparare);

    int top=0;

    for(int i=0;i<n;i++)
    {
        while(top>=2 && cross(stiva[top-2],stiva[top-1],puncte[i])<=EPS)
        {
            top--;
        }
        stiva[top++]=puncte[i];
    }

    int limita_inf=top;

    for(int i=n-2;i>=0;i--)
    {
        while(top>limita_inf && cross(stiva[top-2],stiva[top-1],puncte[i])<=EPS)
            top--;
        stiva[top++]=puncte[i];
    }

    top--;

    fprintf(g,"%d\n",top);

    for(int i=0;i<top;i++)
    {
        fprintf(g,"%.12lf %.12lf\n",stiva[i].x,stiva[i].y);

    }

    printf("gata\n");

    fclose(f);
    fclose(g);
    
    return 0;
}