Cod sursa(job #3300771)

Utilizator David-OvidiuDavid Ovidiu David-Ovidiu Data 18 iunie 2025 21:33:33
Problema Infasuratoare convexa Scor 100
Compilator c-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <stdlib.h>
#include <stdio.h>
#include <math.h>

typedef struct point{
    double x, y;
} point;

point min;

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

double slope( point a, point b )
{
    if ( a.x == b.x )
    {
        if ( a.y < b.y )
            return INFINITY;
        else
            return -INFINITY;
    }
    else
        return (b.y-a.y)/(b.x-a.x);
}

int cmp( const void* a, const void* b )
{
    point *c = (point *)a;
    point *d = (point *)b;
    if ( slope(min,*c) > slope (min,*d) )
        return 1;
    if ( slope(min,*c) == slope (min,*d) )
    {
        if ( c->x > d->x )
            return 1;
        if ( c->x == d->x )
        {
            if ( c->y > d->y )
                return 1;
            else
                return 0;
        }
        else 
            return 0;
    }
    else
        return 0;
}

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

    int n;
    point v[120001];
    fscanf(f,"%d",&n);
    for ( int i = 0 ; i < n ; i++ )
    {
        fscanf(f,"%lf %lf",&v[i].x,&v[i].y);
        if ( v[i].x < min.x || i == 0 )
        {
            min = v[i];
        }
        if ( v[i].x == min.x && v[i].y == min.y )
        {
            min.y = v[i].y;
        }
    }
    qsort(v,n,sizeof(point),cmp); 

    point st[120001];
    int k = 2,i = 2;
    st[0] = v[0];
    st[1] = v[1];
    while ( i < n )
    {
        while ( angle(st[k-2],st[k-1],v[i]) <= 0 && k >= 2 )
        {
            k--;
        }
        st[k] = v[i];
        k++;
        i++;
    }

    fprintf(out,"%d\n",k);
    for ( int j = 0 ; j < k ; j++ )
    {
        fprintf(out,"%.12lf %.12lf \n",st[j].x,st[j].y);
    }
    fclose(out);
    fclose(f);
    return 0;
}