Cod sursa(job #3300912)

Utilizator razvan.14Andronie Razvan razvan.14 Data 20 iunie 2025 01:34:07
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 2.3 kb
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define MAX 120000


typedef struct{
    double x,y;
}point;

point points[MAX], infasuratoare[MAX];
int N, top=0;

// aici gasim indexul punctului de start pentru infasuratoarea noastra
int find_starting_point()
{
    int idx=0;
    for(int i=1; i<N; i++)
    {
        if((points[i].y < points[idx].y)|| (points[i].y == points[idx].y && points[i].x < points[idx].x))
        {
            idx=i;
        }
    }
    return idx;
}

//aici verificam sensul rotirii la 3 unghiuri

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);
}

//aici facem functia de comparatie pentru sortarea punctelor ramase fata de unghiul format cu punctul de start
int compare(const void *x, const void *y)
{
    point p1=*(point*)x;
    point p2=*(point*)y;
    double val=cross(points[0], p1,p2);
    if(val==0)
    {
        double d1 = (p1.x - points[0].x)*(p1.x - points[0].x) + (p1.y - points[0].y)*(p1.y - points[0].y);
        double d2 = (p2.x - points[0].x)*(p2.x - points[0].x) + (p2.y - points[0].y)*(p2.y - points[0].y);
        if(d1<d2)
        return -1;
        else return 1;
    }
    if(val>0)
    return -1;
    else return 1;
}

void graham()
{
    int start=find_starting_point();
    point aux=points[0];
    points[0]=points[start];
    points[start]=aux;

    qsort(points+1,N-1,sizeof(point), compare);
    infasuratoare[0]=points[0];
    infasuratoare[1]=points[1];
    top=2;

    for (int i=2; i<N; i++) 
    {
        while (top>=2&&cross(infasuratoare[top-2],infasuratoare[top-1], points[i]) <= 0)
            top--;  
        infasuratoare[top++] = points[i];
    }


}
int main(void)
{
    FILE *fin=NULL, *fout=NULL;
    if((fin=fopen("infasuratoare.in","r"))==NULL)
    {
        fprintf(stderr,"eroare la deschidere fisier");
        exit(-1);
    }
    if((fout=fopen("infasuratoare.out","w"))==NULL)
    {
        fprintf(stderr,"eroare la deschidere fisier");
        exit(-1);
    }

    fscanf(fin,"%d", &N);
    for(int i=0; i<N; i++)
    {
        fscanf(fin,"%lf %lf", &points[i].x, &points[i].y);
    }

    graham();
    fprintf(fout,"%d\n",top);
    for(int i=0; i<top; i++)
    {
        fprintf(fout,"%.6lf %.6lf\n", infasuratoare[i].x, infasuratoare[i].y);

    }
    fclose(fin);
    fclose(fout);

    return 0;
}