Cod sursa(job #3300622)

Utilizator frigura-iliasa.flavia-mihaelaFrigura-Iliasa Flavia-Mihaela frigura-iliasa.flavia-mihaela Data 17 iunie 2025 23:59:24
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.85 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <limits.h>

#define MAX_PUNCTE 120001

typedef struct
{
    double x, y;
}punct;

punct puncte[MAX_PUNCTE];
int stiva[MAX_PUNCTE];
int varf=0;
int n;
int x_minim=1e18,y_minim=1e18,pozitie_minima;

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

int compara(const void* p1, const void* p2)
{
    punct a=*(punct*)p1;
    punct b=*(punct*)p2;
    double det=determinant(puncte[0],a,b);
    return (det>0)?-1:(det<0)?1:0;
}

int main()
{
    FILE *f,*out;
    if((f=fopen("infasuratoare.in","r"))==NULL)
    {
        perror("Nu se poate deschide fisierul.");
        exit(-1);
    }
    if((out=fopen("infasuratoare.out","w"))==NULL)
    {
        perror("Nu se poate deschide fisierul.");
        exit(-1);
    }
    fscanf(f,"%d",&n);
    for(int i=0;i<n;i++)
    {
        fscanf(f,"%lf %lf",&puncte[i].x,&puncte[i].y);
    }
    for(int i=0;i<n;i++)
    {
        if(puncte[i].x<x_minim)
        {
            x_minim=puncte[i].x;
        }
    }
    for(int i=0;i<n;i++)
    {
        if(puncte[i].x==x_minim&&puncte[i].y<y_minim)
        {
            y_minim=puncte[i].y;
            pozitie_minima=i;
        }
    }
    punct temp=puncte[0];
    puncte[0]=puncte[pozitie_minima];
    puncte[pozitie_minima]=temp;
    qsort(puncte+1,n-1,sizeof(punct),compara);
    puncte[n]=puncte[0];
    stiva[0]=0;
    stiva[1]=1;
    varf=1;
    for(int i=2;i<=n;i++)
    {
        while(varf>0&&determinant(puncte[stiva[varf-1]],puncte[stiva[varf]],puncte[i])<0)
            varf--;
        stiva[++varf]=i;
    }
    fprintf(out,"%d\n",varf);
    for(int i=1;i<=varf;i++)
        fprintf(out,"%.6lf %.6lf\n",puncte[stiva[i]].x,puncte[stiva[i]].y);
    fclose(f);
    fclose(out);
    return 0;
}